백준 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.
백준 17779번 게리맨더링 2 - C++ 풀이
1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 1. 모든 (x, y, d1, d2) 쌍에 대해 선거구 나누기를 하여 최적화한다. 가능한 모든 (x, y, d1, d2) 쌍은 N^4개, 선거구 나누기 시뮬레이션에 O(N^2)의 시간 복잡도가 소요되므로, 전체 시간 복잡도는 O(N^6). 이때 N=20이므로 브루트 포스로 해결할 수 있다. 선거구 나누기 시뮬레이션은 주어진 조건을 잘 구현하면 되고, 경계선으로 둘러싸인 5번 선거구는 DFS로 처리해주었다. #include #include #include using namespace std; const int INF = 987654321; int N; int A[20][20]; int board[20][20]; bool va..
2022. 9. 18.
