백준 1309번 동물원 - C++ 풀이
1. dp(idx, prev) : (idx-1) 번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수 2. prev = 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 1) + dp(idx+1, 2) 3. prev > 0 이면, dp(idx, prev) = dp(idx+1, 0) + dp(idx+1, 3-prev) 1. dp(idx, prev) : (idx-1)번째 행의 상태가 prev일 때 idx번 행~마지막까지 채우는 방법의 수 dp(idx, prev)를 위와 같이 정의하자. 사자가 세로로 붙어있을 수 없으므로 prev값이 필요하다. 이때 사자가 가로로 붙어있을 수 없으므로 한 행 내의 사자 상태는 아예 없거나, 오른쪽 칸에만 있거나, 왼쪽 칸에..
2022. 9. 22.
백준 2931번 가스관 - C++ 풀이
1. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾는다. 2. 끊긴 모든 방향을 다시 이을 수 있는 배관의 위치와 종류를 찾는다. 1. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾는다. 모든 배관에 대해, 끊긴 길의 방향을 모두 찾아둔다. 아래와 같은 상황에서 (2,2)의 | 모양 배관을 보면, 아래 방향으로는 길이 끊겨있다. 이는 곧 (3,2)에서 윗방향으로 잇는 배관이 필요하다는 뜻이므로 기록해둔다. 마찬가지로 (4,2)의 | 모양 배관을 보면, 윗방향으로 길이 끊겨있다. (3,2)에서 아랫방향으로 잇는 배관이 필요하다는 뜻이다. 2. 끊긴 모든 방향을 다시 이을 수 있는 배관의 위치와 종류를 찾는다. 딱 한 개의 배관만 제거했다고 했으므로, 배관이 필요한 칸은 한 개뿐이다. 해당 칸에 필요한 방향..
2022. 9. 22.
