백준 11574 - CYK의 너무너무 재밌는 그래프 만들기 놀이 [Python]

https://www.acmicpc.net/problem/11574

11574번: CYK의 너무너무 재밌는 그래프 만들기 놀이

간단한 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일때

앞서 설명한대로 하면 됨

############### 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 ########

k=1일때 n출력해서 엄청틀렸다

 

dp테이블 하나로도 짤수 있더라,,