백준 문제풀이
백준 11574 - CYK의 너무너무 재밌는 그래프 만들기 놀이 [Python]
Vermeil
2021. 7. 1. 15:32
https://www.acmicpc.net/problem/11574
11574번: CYK의 너무너무 재밌는 그래프 만들기 놀이
N (1 ≤ N ≤ 100)개의 정점의 개수가 주어지고, K (1 ≤ K ≤ 3)개의 가능한 색깔이 주어진다. 각 정점들을 1 부터 N까지 차례로 번호를 매기고, 그 정점들에 K개의 색깔중 하나를 임의로 부여한다.
www.acmicpc.net
간단한 DP
k = 1일때
무조건 1가지이다.
k = 2일때
맨 뒤에 색 1 추가, 혹은 색 2를 추가하는 경우가 있다.
\(dp[n][k] = n번째에서 색 1을 k개 사용하였을 때, 경우의 수\) 라고 하자.
색 1을 붙일 때:
간선을 잇는 경우는 색 2의 개수이고, 잇지 않는 경우는 1가지이므로,
\(dp[n - 1][k - 1] * (n - k + 1)\)
색 2를 붙일 때:
간선을 잇는 경우는 색 1의 개수이고, 잇지 않는 경우는 1가지이므로,
\(dp[n - 1][k] * (k + 1)\)
이 둘을 더한 값이 \(dp[n][k]\)의 값이다.
k = 3일때
앞서 설명한대로 하면 됨
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
############### Main! ###############
MAX = 105
MOD = 1000000007
dp1 = [[0 for _ in range(MAX)] for _ in range(MAX)]
dp2 = [[[0 for _ in range(MAX)] for _ in range(MAX)] for _ in range(MAX)]
dp1[0][0] = 1
dp2[0][0][0] = 1
n, k = map(int, input().split())
if k == 1:
print(1)
exit()
ans = 0
if k == 2:
for i in range(1, n + 1):
for j in range(i + 1):
dp1[i][j] += dp1[i - 1][j - 1] * (i - j + 1) # col 1
dp1[i][j] += dp1[i - 1][j] * (j + 1) # col 2
dp1[i][j] %= MOD
print(sum(dp1[n]) % MOD)
exit()
for i in range(1, n + 1):
for j in range(i + 1):
for c in range(i - j + 1):
dp2[i][j][c] += dp2[i - 1][j - 1][c] * (i - j + 1) # col 1
dp2[i][j][c] += dp2[i - 1][j][c - 1] * (i - c + 1) # col 2
dp2[i][j][c] += dp2[i - 1][j][c] * (j + c + 1) # col 3
dp2[i][j][c] %= MOD
for j in range(n + 1):
ans += sum(dp2[n][j]) % MOD
ans %= MOD
print(ans % MOD)
######## Priest W_NotFoundGD ########
|
cs |
k=1일때 n출력해서 엄청틀렸다
dp테이블 하나로도 짤수 있더라,,