bitmasking

[백준] 1562. 계단 수 - Python

[Gold I] https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스킹을 이용한 DP 문제. 기본적인 아이디어는 2차원 DP를 생각하면 쉽게 떠올릴 수 있는데, dp[N][i] 일 때, dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1] 과 같은 점화식(i==0, i==9 예외) 으로 풀이할 수 있다. 다만 위의 경우는 0부터 9까지 숫자가 모두 등장하는 계단 수 라는 조건을 무시했을 때의 풀이법. 이 문제는 위 조건을 만족하는 수의 개수만을 구해야 하므로, 기존 풀이를 응용하여 풀이할 수 있다. 기존 2차원 배열이 아닌, 3차원 배열로 선..

[백준] 1194. 달이 차오른다, 가자. - Python

[Gold I] https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 기본적으로 상하좌우 4방향으로 뻗어 나가는 흔한 BFS 형식으로 풀이하면 된다. 그런데 이제 비트마스킹을 곁들인. 열쇠와 문이 없다면, 각 row와 column, 그러니까 아래 코드에서는 visited[r][c] 2차원 배열만 채우며 진행하면 될 것이다. 그러나 열쇠가 있으므로.. 예를 들어, a열쇠를 가지고 (0,0)에 도달한 경우와, a열쇠가..

[백준] 14939. 불 끄기 - 파이썬

[Platinum V] https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 백조의 호수 이후로 오랜만에 풀어보는 플래티넘 문제. ^ㅁ^ 풀이 우선, 10x10 배열 - 100칸이기에, 너무 무모한 Brute-Forcing만 아니면, TLE는 나오지 않겠거니 하고 생각했다. 처음 보자마자 떠올린 것은, 한 번 누른 칸은 다시 누를 일이 없지 않을까? 라는 것. 한 번 눌린 칸을 다시 누르게 되면, 5칸이 결국 누르기 전의 상태와 같아지는 ..