본문 바로가기
728x90

비트마스킹3

[python] 백준 14939 불 끄기 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 문제 해결 문제의 이해는 쉽지만 풀기 많이 어려웠던 문제 어디서부터 시작해야할지 많이 어렵다. 이 때 불 키고/끄고를 비트마스크를 이용해서 풀 수 있다고 하는데 어려워서 여러 코드를 확인하였다. 가장 중요한 것은 '첫 번째' 행의 불이 켜져있든 꺼져있든 스위치를 누루는 경우의 수를 모두 탐색하는 것이다. 이유는 첫 번째 행이 꺼져있어서 눌러 불을 켜도 다음 밑에 있는 스위치를 눌러서 다.. 2024. 3. 2.
[python] 백준 1062 가르침 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문제해결 anta와 tica 사이 알파벳을 봐야하지만 중요한 것은 'a', 'n', 't', 'i', 'c' 는 무조건 들어가야한다. 즉 k=5: learned = [0]*123 for x in {'a','n','t','i','c'}: learned[ord(x)] = 1 for teach in list(combinations(res,k-5)): for t in teach: learned[o.. 2023. 5. 5.
[python] 백준 1562 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 개념 정리 비트 연산자 AND 연산 (&): 대응하는 두 비트가 모두 1일 때, 1 반환 OR 연산 (|): 대응하는 두 비트가 하나라도 1일 때, 1 반환 XOR 연산 (^): 대응하는 두 비트가 서로 다르면, 1 반환 왼쪽 Shift (): 오른쪽으로 비트를 옮긴다. 1011 & 1111 # 1011 1011 | 1111 # 1111 1011 ^ 1111 # 0100 00001010 > 2 # 000010 문제 해결 먼저 비트마스크를 알아야 한다. dp[i][k]는 마지막 숫자가 i이고 0~9 숫자 유무를1,0으로 .. 2023. 5. 5.
728x90