Atcoder Educational DP Contest
여러 유형의 DP 문제를 풀어보자
- A - Frog 1
- B - Frog 2
- C - Vacation
- D - Knapsack 1
- E - Knapsack 2
- F - LCS
- G - Longest Path
- H - Grid 1
- I - Coins
- J - Sushi
- K - Stones
- L - Deque
- N - Slimes
- O - Matching
- P - Independent Set
- 대회 링크: https://atcoder.jp/contests/dp
- 총 26 문제가 있는데 시간 날 때마다 풀어보도록 하자. 다 풀 수는 있겠지?
- $\operatorname{dp}[i]$를 개구리가 $i$번 돌까지 오는데 필요한 최소 비용이라고 하자. 개구리가 $i$번 돌에 위치하고 있다면 점프 이전에는 $i-1$번 또는 $i-2$번 돌에 위치했을 것이다
- 그러므로 $\operatorname{dp}[i] = \min(\operatorname{dp}[i - 1] + |h_{i-1} - h_i|,\, \operatorname{dp}[i - 2] + |h_{i-2} - h_i|)$이며 초깃값으로 $\operatorname{dp}[1] = 0, \operatorname{dp}[2] = |h_1 - h_2|$이다
- 정답은 $\operatorname{dp}[N]$이며 전체 알고리즘의 시간 복잡도는 $O(N)$이다
def cost(i, j):
return abs(array[i] - array[j])
def solution():
global array
N = int(input())
array = list(map(int, input().split()))
inf = float("inf")
dp = [inf] * N
dp[0] = 0
dp[1] = cost(0, 1)
for i in range(2, N):
dp[i] = min(dp[i - 1] + cost(i - 1, i), dp[i - 2] + cost(i - 2, i))
answer = dp[N - 1]
print(answer)
solution()
- Frog 1 문제에선 $2$가지 경우만 고려하면 됐다. 여기선 $K$개의 경우를 고려하자
- 전체 알고리즘의 시간 복잡도는 $O(NK)$이다
def cost(i, j):
return abs(array[i] - array[j])
def solution():
global array
N, K = map(int, input().split())
array = list(map(int, input().split()))
inf = float("inf")
dp = [inf] * N
dp[0] = 0
dp[1] = cost(0, 1)
for i in range(2, N):
for j in range(1, K + 1):
prev = max(i - j, 0)
dp[i] = min(dp[prev] + cost(prev, i), dp[i])
answer = dp[N - 1]
print(answer)
solution()
- $\operatorname{dp}[i][t]$를 $i$번째 날에 $a,b,c$ 중 $t$ 활동을 했을 때 얻을 수 있는 최대 행복 점수라고 하자
- 전날에 안 한 활동 중 하나를 골라서 했을 때 행복 점수가 더 큰 걸로 선택하면 된다. 따라서 점화식은 다음과 같다
- $\operatorname{dp}[i][a] = A[i] + \max(\operatorname{dp}[i - 1][b], \operatorname{dp}[i-1][c])$
- $\operatorname{dp}[i][b] = B[i] + \max(\operatorname{dp}[i - 1][a], \operatorname{dp}[i - 1][c])$
- $\operatorname{dp}[i][c] = C[i] + \max(\operatorname{dp}[i - 1][a], \operatorname{dp}[i - 1][b])$
- 정답은 $\max(\operatorname{dp}[N][a], \operatorname{dp}[N][b], \operatorname{dp}[N][c])$이며 전체 알고리즘의 시간 복잡도는 $O(N)$이다
def solution():
N = int(input())
A, B, C = [], [], []
for _ in range(N):
a, b, c = map(int, input().split())
A.append(a)
B.append(b)
C.append(c)
dp = [[0] * 3 for _ in range(N)] # 0 = a, 1 = b, 2 = c
dp[0] = [A[0], B[0], C[0]]
for i in range(1, N):
dp[i][0] = A[i] + max(dp[i - 1][1], dp[i - 1][2])
dp[i][1] = B[i] + max(dp[i - 1][0], dp[i - 1][2])
dp[i][2] = C[i] + max(dp[i - 1][0], dp[i - 1][1])
answer = max(dp[N - 1])
print(answer)
solution()
- 웰노운 배낭 문제이다. 배낭에 물건을 담는 경우의 수는 각 물건을 배낭에 넣거나 안 넣거나로 $2^N$이지만 배낭 용량은 $W$에 바운드 됨에 집중하자. 그럼 $i$번째 물건까지 고려했을 때 $1\sim W$ 무게별로 최대 가치를 저장함으로써 DP를 사용해 해결할 수 있게 된다
- 전체 알고리즘의 시간 복잡도는 $O(NW)$이며 무게를 역순으로 탐색하면 공간 복잡도는 $O(W)$가 된다
def solution():
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (W + 1)
for w, v in items:
for t in range(W, w - 1, -1):
dp[t] = max(dp[t - w] + v, dp[t])
answer = dp[W]
print(answer)
solution()
- $O(NW)$는 시간 초과이다. 대신 물건의 가치가 최대 $10^3$임을 이용하자
- 배낭에 담을 수 있는 물건의 가치 합 $V$는 최대 $\sum\limits_{i=1}^{N}v_i$이다. $1$과 $V$ 사이의 가치에 대해 해당 가치를 만드는 데 필요한 최소 배낭 용량을 기록하자. 그럼 이것이 $W$를 초과하지 않는 것 중 최대 가치가 정답이며 시간 복잡도는 $O(NV)$이다
def solution():
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
inf = float("inf")
V = sum(map(lambda x: x[1], items))
dp = [inf] * (V + 1)
dp[0] = 0
for w, v in items:
for t in range(V, v - 1, -1):
dp[t] = min(dp[t - v] + w, dp[t])
for v in range(V, 0, -1):
if dp[v] <= W:
print(v)
return
solution()
- 웰노운 문제이다. $\operatorname{dp}[i][j]$를 $s$의 $i$번째 문자까지, 그리고 $t$의 $j$번째 문자까지 고려했을 때 LCS의 길이라고 하자
- 만약, $s_i = t_j$라면 $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j - 1] + 1$이다
- 그렇지 않다면 적어도 둘 중 하나는 LCS에 포함되지 않으므로 $\operatorname{dp}[i][j] = \max(\operatorname{dp}[i - 1][j], \operatorname{dp}[i][j - 1])$이다
- LCS의 길이는 구했으니 이를 역추적하자. $i = |s|, j = |t|$에서 시작해 둘 중 하나가 $0$이 될 때까지 역추적할 것이다. $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j]$라면 $s_i$는 LCS에 포함되지 않으며 $i$를 $i-1$로 갱신하자. 반대로 $\operatorname{dp}[i][j] = \operatorname{dp}[i][j - 1]$라면 $j$를 $j-1$로 갱신하자. 둘 다 아니라면 $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j - 1] + 1$인 것으로 $s_i =t_j$이니 이를 배열에 추가하고 $i$를 $i-1$로, $j$를 $j-1$로 갱신하자
- LCS의 맨 뒤부터 역추적했으므로 배열을 뒤집고 결합해야 LCS가 된다. 시간 복잡도와 공간 복잡도는 $O(|s|\cdot |t|)$이다
def solution():
s = input().rstrip()
t = input().rstrip()
n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
s_i = s[i - 1]
for j in range(1, m + 1):
t_j = t[j - 1]
if s_i == t_j:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
track = []
i, j = n, m
while i > 0 and j > 0:
s_i = s[i - 1]
if dp[i][j] == dp[i - 1][j]:
i -= 1
elif dp[i][j] == dp[i][j - 1]:
j -= 1
else:
track.append(s_i)
i -= 1
j -= 1
answer = "".join(track[::-1])
print(answer)
solution()
- $\operatorname{dp}[u]$를 $u$번 노드를 시작으로 할 때 얻을 수 있는 최장 경로의 길이라고 하자
- $u$번 노드에서 $v_1, v_2, \dots, v_k$번 노드로 향하는 간선이 있다고 하면 그래프에 사이클이 없으므로 $\operatorname{dp}[u] = 1 + \max\limits_{i \in \{1,2,\dots, k\}}\operatorname{dp}[v_i]$를 만족한다
- 초깃값으로 $u$번 노드의 진출차수가 $0$인 경우 $\operatorname{dp}[u] = 0$이다
- 정답은 $\max(\operatorname{dp})$이며 각 노드와 간선을 $O(1)$번만 확인하므로 전체 알고리즘의 시간 복잡도는 $O(N + M)$이다
import sys
sys.setrecursionlimit(10**5 + 2)
def dfs(graph, u, dp):
if dp[u] >= 0:
return dp[u]
lengths = []
for v in graph[u]:
length = dfs(graph, v, dp)
lengths.append(length)
dp[u] = 1 + max(lengths) if lengths else 0
return dp[u]
def solution():
N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
x, y = map(int, input().split())
graph[x].append(y)
dp = [-1] * (N + 1)
for u in range(1, N + 1):
dfs(graph, u, dp)
answer = max(dp)
print(answer)
solution()
- $\operatorname{dp}[i][j]$를 $(1,1)$에서 $(i, j)$까지 이동하는 경우의 수라고 하자
- 오른쪽과 아래로만 이동이 가능하므로 직전엔 현재의 왼쪽 또는 위에 위치했을 것이다. 따라서 다음과 같은 점화식을 세울 수 있다
- $\operatorname{dp}[i][j] = \operatorname{dp}[i - 1][j] + \operatorname{dp}[i][j - 1]$, 단, $(i,j),(i-1, j), (i, j-1)$은 빈 공간이며 $\operatorname{dp}[0][\cdot]$과 $\operatorname{dp}[\cdot][0]$은 $0$이다
- 바텀업 방식으로 행은 $1$행부터, 행마다 열은 $1$열부터 순회하면 되며 초깃값으로 $\operatorname{dp}[1][1] = 1$이다
- 최종적으로 정답은 $\operatorname{dp}[H][W]$이며 전체 알고리즘의 시간 복잡도는 $O(HW)$이다
def solution():
wall = "."
mod = 10**9 + 7
H, W = map(int, input().split())
grid = [input().rstrip() for _ in range(H)]
dp = [[0] * W for _ in range(H)]
dp[0][0] = 1
for r in range(H):
for c in range(W):
if grid[r][c] != ".":
continue
if r > 0 and grid[r - 1][c] == ".":
dp[r][c] += dp[r - 1][c]
if c > 0 and grid[r][c - 1] == ".":
dp[r][c] += dp[r][c - 1]
dp[r][c] %= mod
answer = dp[H - 1][W - 1]
print(answer)
solution()
- $\operatorname{dp}[i][k]$를 $1$번부터 $i$번 동전까지 던졌을 때 앞면이 $k$개 나올 확률이라고 하자
- 만약 $i$번 동전을 던져 앞면이 나온다면 $\operatorname{dp}[i][k] = \operatorname{dp}[i - 1][k - 1] \cdot p_i$이다 (단, $k > 0$)
- 그렇지 않고 $i$번 동전을 던져 뒷면이 나온다면 $\operatorname{dp}[i][k] = \operatorname{dp}[i - 1][k] \cdot (1 - p_i)$이다
- 따라서 $\operatorname{dp}[i][k] = \operatorname{dp}[i - 1][k - 1] \cdot p_i + \operatorname{dp}[i - 1][k] \cdot (1 - p_i)$이다 ($k=0$이면 앞의 항은 무시)
- 최종적으로 앞면이 뒷면보다 많이 나올 확률을 구해주면 정답이다
- 전체 알고리즘의 시간 복잡도는 $O\left(N^2\right)$이며 $k$를 역순으로 탐색하면 공간 복잡도는 $O(N)$이다
def solution():
N = int(input())
probs = list(map(float, input().split()))
dp = [0] * (N + 1)
dp[0] = 1
for i, p in enumerate(probs, start=1):
for k in range(i, -1, -1):
dp[k] *= (1 - p)
if k > 0:
dp[k] += dp[k - 1] * p
answer = sum(dp[(N + 1) // 2:])
print(answer)
solution()
- 앞 번호의 문제 중 가장 어려운 문제이다. 쉬운 버전의 문제를 먼저 풀어 인사이트를 얻고 풀이를 확장할 것이다
- 모든 접시에 초밥이 $1$개만 있다고 가정해보자. 그럼 $N$개의 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값은 다음과 같다
- $\text{$N$개의 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값} = \text{남은 $N$개의 초밥 중 초밥 $1$개를 먹기 위해 주사위를 굴리는 횟수의 기댓값} + \cdots + \text{남은 $1$개의 초밥 중 초밥 $1$개를 먹기 위해 주사위를 굴리는 횟수의 기댓값}$
- 즉, 초밥을 먹을 확률은 $N$개의 초밥 중 현재 $x$개가 남아있다고 할 때 $\frac{x}{N}$이다. 이를 먹는 데 성공할 때까지 시도할 것이니 주사위를 굴리는 횟수는 기하 분포를 따르게 돼어 기댓값은 확률의 역수가 된다
- 따라서 $N$개의 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값은 $\frac{N}{N} + \frac{N}{N - 1} + \cdots + \frac{N}{1}$이다. 이건 사실 백준 쿠폰 문제와 동일하다
- 문제는 모든 접시에 $1$개의 초밥만 있는 게 아니라는 것이다. $2$개일 수도 있고 $3$개일 수도 있다. 일단 문제를 쉽게 만들고자 모든 접시에 초밥은 $1$개 또는 $2$개만 있다고 하자
- 처음에 주사위를 굴리면 $1$의 확률로 초밥을 먹는다. 이때 초밥이 $1$개 있는 접시일 수도 있고 $2$개 있는 접시일 수도 있다. 만약 운 좋게 $2$개 있는 접시를 골랐다면 다음번에도 $1$의 확률로 초밥을 먹을 수 있다. 그게 아니라면 $N-1$개의 초밥만 남아있으므로 $\frac{N - 1}{N}$의 확률로 초밥을 먹을 수 있다
- 즉, 주사위를 굴려 나온 번호의 접시에 초밥이 몇 개 있냐에 따라 다음에 초밥을 먹을 수 있는 확률이 달라진다
- 이를 추적하자. 초밥이 $1$개 있는 접시의 개수를 $x_1$이라 하고 $2$개 있는 접시의 개수를 $x_2$라 하고 $\operatorname{dp}[x_1][x_2]$를 모든 초밥을 먹기 위해 주사위를 굴리는 횟수의 기댓값이라 하자
- 초밥이 있는 접시를 고를 확률은 $\frac{x1 + x2}{N}$이다. 이때 초밥이 $1$개 있는 접시를 고를 확률은 $\frac{x_1}{x_1 + x_2}$이고 $2$개 있는 접시를 고를 확률은 $\frac{x_2}{x_1 + x_2}$이다
- 우선 초밥이 있는 접시를 고르고자 기댓값에 해당하는 $\frac{N}{x1 + x2}$번만큼 주사위를 굴려야 한다. 그리고 초밥이 몇 개 있는 접시냐에 이후 기댓값이 달라진다. 이때 초밥이 $2$개 있는 접시를 고르면 해당 접시엔 $1$개만 남게 되므로 초밥이 $1$개 있는 접시의 개수가 $1$ 증가함에 유의하자
- 따라서 $\operatorname{dp}[x_1][x_2] = \frac{N}{x_1 + x_2} + \frac{x_1}{x_1 + x_2} \cdot \operatorname{dp}[x_1 - 1][x_2] + \frac{x_2}{x_1 + x_2} \cdot \operatorname{dp}[x_1 + 1][x_2 - 1]$이 성립한다
- 이를 접시에 초밥이 최대 $3$개 있는 것까지 확장하면 점화식은 다음과 같다
- $\operatorname{dp}[x_1][x_2][x_3] = \frac{N}{x_1 + x_2 + x_3} + \frac{x_1}{x_1 + x_2 + x_3} \cdot \operatorname{dp}[x_1 - 1][x_2][x_3] + \frac{x_2}{x_1 + x_2 + x_3} \cdot \operatorname{dp}[x_1 + 1][x_2 - 1][x_3] + \frac{x_3}{x_1 + x_2 + x_3} \cdot \operatorname{dp}[x_1][x_2 + 1][x_3 - 1]$
- 초깃값으로 $\operatorname{dp}[0][0][0] = 0$이며 $x_1 > 0, x_2 = 0, x_3 = 0$인 경우 쿠폰 문제와 동일하게 처리하자
- 전체 알고리즘의 시간 복잡도와 공간 복잡도는 $O\left(N^3\right)$이며 $x_1 + x_2 + x_3 = N$이므로 $N^3$의 계수가 작아 제한 시간 안에 동작한다
def compute_hamonic_number(n):
return sum(1 / k for k in range(1, n + 1))
def eat_sushi(x1, x2, x3, n, dp):
if dp[x1][x2][x3] >= 0:
return dp[x1][x2][x3]
if x2 == 0 and x3 == 0:
dp[x1][x2][x3] = n * compute_hamonic_number(x1)
return dp[x1][x2][x3]
s = x1 + x2 + x3
t = n
if x1 > 0:
t += x1 * eat_sushi(x1 - 1, x2, x3, n, dp)
if x2 > 0:
t += x2 * eat_sushi(x1 + 1, x2 - 1, x3, n, dp)
if x3 > 0:
t += x3 * eat_sushi(x1, x2 + 1, x3 - 1, n, dp)
t /= s
dp[x1][x2][x3] = t
return t
def solution():
N = int(input())
array = list(map(int, input().split()))
dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
xs = [0] * 3
for a in array:
xs[a - 1] += 1
x1, x2, x3 = xs
answer = eat_sushi(x1, x2, x3, N, dp)
print(answer)
solution()
- $\operatorname{dp}[i]$를 본인 차례에 돌이 $i$개 남았을 때 게임의 승패 여부라고 하자 ($1$이면 승리, $0$이면 패배)
- 더미에 최소 $a_1$개의 돌이 남아있어야 돌을 제거할 수 있므로 초깃값으로 $\operatorname{dp}[0] \sim \operatorname{dp}[a_1 - 1]$은 $0$이다
- 현재 차례에 몇 개의 돌을 제거해도 남은 돌의 개수가 $\text{P}$-포지션에 해당한다면 현재 차례의 돌의 개수는 $\text{N}$-포지션이다. 반대로 현재 차례에서 $\text{N}$-포지션을 만들 수 있는 방법이 적어도 하나 존재하면 현재 차례의 돌의 개수는 $\text{P}$-포지션이다 ($\text{P}$-포지션은 승리, $\text{N}$-포지션은 패배). 따라서 점화식은 다음과 같다
- $\operatorname{dp}[i] = \begin{cases}
\\
\, 0 & \text{if } i < a_1 \\[1.3em]
\, 0 & \text{if } \displaystyle\prod_{1\le j \le N, \, i \ge a_j} \operatorname{dp}[i - a_j] = 1 \\[0.5em]
\, 1 & \text{if } \displaystyle\prod_{1\le j \le N, \, i \ge a_j} \operatorname{dp}[i - a_j] = 0
\end{cases}$
- $\operatorname{dp}[K]$가 $1$이면 Taro가 승리하고 $\operatorname{dp}[K]$가 $0$이라면 Jiro가 승리한다. 전체 알고리즘의 시간 복잡도는 $K=10^5$이고 $a_N = N$인 최악의 경우 $O(NK)$이다
def solution():
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = [0] * (K + 1)
for i in range(A[0], K + 1):
if all(dp[i - a] for a in A if i - a >= 0):
dp[i] = 0
else:
dp[i] = 1
if dp[K]:
answer = "First"
else:
answer = "Second"
print(answer)
solution()
- 난생처음 보는 유형이다 (꽤 흥미로움). 각 플레이어의 목적이 서로 다름을 고려해줘야 한다
- $\operatorname{dp}[i][j]$를 $a_i \sim a_j$만 존재하는 상황에서 각 플레이어가 최적으로 플레이 했을 때 게임 종료시의 $X-Y$라고 하자. $j-i+1$은 구간의 길이 $l$로 만약 $N$과 $l$의 홀짝성이 같다면 Taro 차례이고 다르다면 Jiro 차례이다
- 누구 차례냐에 따라 목적이 다르기에 상태 전이가 달라진다. Taro는 $X-Y$를 최대화하고 Jiro는 $X-Y$를 최소화한다. 이를 고려한 점화식은 다음과 같다
- $\operatorname{dp}[i][j] = \begin{cases}
\, \max(\operatorname{dp}[i + 1][j] + a_i , \operatorname{dp}[i][j - 1] + a_j) & \text{if } N - l \text{ is even} \\ \\
\, \min(\operatorname{dp}[i + 1][j] - a_i , \operatorname{dp}[i][j - 1] - a_j) & \text{if } N - l \text{ is odd}
\end{cases}$
- 단, $l = j - i + 1$이고 초깃값은 다음과 같다. $\operatorname{dp}[i][i] = \begin{cases}
\, a_i & \text{if } N \text{ is odd} \\
\, -a_i & \text{if } N \text{ is even}
\end{cases}$
- 정답은 $\operatorname{dp}[1][N]$이며 전체 알고리즘의 시간 복잡도는 $O\left(N^2\right)$이다. 바텀업으로 구현할 때 구간의 길이가 작은 순으로 탐색해야 함을 잊지 말자
def solution():
N = int(input())
array = list(map(int, input().split()))
dp = [[None] * N for _ in range(N)]
for i in range(N):
if N % 2 == 1:
dp[i][i] = array[i]
else:
dp[i][i] = -array[i]
for length in range(2, N + 1):
for i in range(N - length + 1):
j = i + length - 1
if (N - length) % 2 == 0:
dp[i][j] = max(dp[i + 1][j] + array[i], dp[i][j - 1] + array[j])
else:
dp[i][j] = min(dp[i + 1][j] - array[i], dp[i][j - 1] - array[j])
answer = dp[0][N - 1]
print(answer)
solution()
- 파일 합치기 문제와 동일한 웰노운 구간 DP 문제이다 (처음 접하면 어렵다)
- 슬라임을 합칠 때 인접한 두 슬라임만 합칠 수 있다. 따라서 임의의 합쳐진 슬라임은 연속된 구간의 슬라임을 합친 꼴이 된다
- $\operatorname{dp}[i][j]$를 $i$번째 슬라임부터 $j$번째 슬라임을 하나의 슬라임으로 합칠 때 발생하는 비용의 최솟값이라 하자. 그럼 점화식은 다음과 같다
- $\operatorname{dp}[i][j] = \sum\limits_{l = i}^{j} a_l + \min\limits_{i \le k < j}\{\operatorname{dp}[i][k] + \operatorname{dp}[k + 1][j]\}$
- 초깃값으로 $\operatorname{dp}[i][i] = 0$이다
- 누적 합을 $O\left(N^2\right)$에 전처리 해두면 $i$번째 슬라임부터 $j$번째 슬라임을 합친 슬라임의 크기를 $O(1)$에 알 수 있다. 임의의 $\operatorname{dp}[i][j]$를 결정하는 게 $O(N)$이며 가능한 $(i,j)$ 상태의 개수는 $O\left(N^2\right)$이므로 전체 알고리즘의 시간 복잡도는 $O\left(N^3\right)$이다
- 바텀업 구현시 길이($=j-i+1$)를 $2$부터 $N$까지 오름차순으로 순회해야 됨에 주의하자. 정답은 $\operatorname{dp}[1][N]$이다
from itertools import accumulate
def solution():
inf = float("inf")
N = int(input())
array = list(map(int, input().split()))
prefix_sums = [*accumulate(array, initial=0)]
dp = [[inf] * N for _ in range(N)]
for i in range(N):
dp[i][i] = 0
for length in range(2, N + 1):
for i in range(N - length + 1):
j = i + length - 1
size = prefix_sums[j + 1] - prefix_sums[i]
for k in range(i, j):
dp[i][j] = min(dp[i][k] + dp[k + 1][j] + size, dp[i][j])
answer = dp[0][N - 1]
print(answer)
solution()
- $1$번부터 $i-1$번 남자까지 매칭됐다고 했을 때 이제 $i$번 남자와 적합한 여자를 매칭시켜보자. 현재까지 매칭된 여자 상태의 비트마스크를 $b$라 할 때 여태까지 매칭된 쌍의 수는 $i-1$이므로 $\operatorname{bitcount(b)} = i-1$인 경우만 고려해야 한다 ($\operatorname{bitcount(b)}$는 $b$의 $1$ 개수). 따라서 $0$부터 $2^N - 2$까지의 가능한 $b$에 대해 $i = \operatorname{bitcount(b)} + 1$로 설정하면 된다
- $\operatorname{dp}[b]$를 여자 매칭 상태의 비트마스크가 $b$일 때 가능한 매칭 경우의 수라고 하자. $i$번 남자와 적합한 여자 번호가 $i_1, \dots, i_m$일 때 $b$의 $i_k$번째 비트가 이미 $1$이라면 그 여자와는 매칭시킬 수 없다. 그렇지 않다면 매칭 가능하므로 $\operatorname{dp}[b \operatorname{|} 2^{i_k}]$에 $\operatorname{dp}[b]$를 더해주자 (단, $\operatorname{|}$는 bitwise OR)
- 초깃값으로 $\operatorname{dp}[0] = 1$이며 정답은 $\operatorname{dp}[2^N - 1]$이다
- 전체 알고리즘의 시간 복잡도는 $O\left(N 2^N\right)$이며 공간 복잡도는 $O\left(2^N\right)$이다
def solution():
mod = 10**9 + 7
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
max_bitmask = 2**N - 1
dp = [0] * (max_bitmask + 1)
dp[0] = 1
for b in range(max_bitmask):
if dp[b] == 0:
continue
i = bin(b).count("1") + 1
compatible = matrix[i - 1]
for j in range(N):
b_next = b | (1 << j)
if not compatible[j] or b_next == b:
continue
dp[b_next] += dp[b]
dp[b_next] %= mod
answer = dp[max_bitmask]
print(answer)
solution()
- 루트 노드를 $1$번 노드로 칭하자 (어차피 동일한 트리이므로 뭐든 상관없다)
- $\operatorname{dp}_b[u]$를 $u$번 노드가 검은색일 때 가능한 서브트리의 경우의 수라고 하자 ($\operatorname{dp}_w[u]$는 $u$가 흰색인 경우)
- $u$번 노드가 검은색이면 그의 자식 노드는 모두 흰색이어야 한다. 자식끼리는 인접해 있지 않으니 색깔은 서로 독립이다. 따라서 $v_i$를 $u$의 $i$번째 자식이라 할 때 $\operatorname{dp}_b[u] = \prod\limits_{i=1}^{k} \operatorname{dp}_w[v_i]$이다 ($u$번 노드의 자식은 총 $k$개)
- 반대로 $u$번 노드가 흰색이면 자식 노드의 색깔은 상관없으므로 $\operatorname{dp}_w[u] = \prod\limits_{i=1}^{k} (\operatorname{dp}_b[v_i] + \operatorname{dp}_w[v_i])$이다. 초깃값으로 $u$번 노드가 리프 노드인 경우 $\operatorname{dp}_b[u] = 1, \operatorname{dp}_w[u] = 1$이다
- 정답은 $\operatorname{dp}_b[1] + \operatorname{dp}_w[1]$이며 이를 $10^9+7$로 나눈 나머지를 출력해야 함을 잊지 말자
import sys
sys.setrecursionlimit(10**5 + 2)
def dfs(tree, node, parent, dp_black, dp_white, mod):
dp_black[node] = 1
dp_white[node] = 1
for child in tree[node]:
if child == parent:
continue
dfs(tree, child, node, dp_black, dp_white, mod)
dp_black[node] *= dp_white[child]
dp_black[node] %= mod
dp_white[node] *= (dp_black[child] + dp_white[child]) % mod
dp_white[node] %= mod
def solution():
N = int(input())
tree = [[] for _ in range(N + 1)]
for _ in range(N - 1):
x, y = map(int, input().split())
tree[x].append(y)
tree[y].append(x)
mod = 10**9 + 7
root, none = 1, 0
dp_black, dp_white = [0] * (N + 1), [0] * (N + 1)
dfs(tree, root, none, dp_black, dp_white, mod)
answer = (dp_black[root] + dp_white[root]) % mod
print(answer)
solution()