[백준(파이썬/Python)] 2225_합분해 - DP

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

2225번: 합분해

 

DP를 맨 처음에 공부할 때 즈음에 배우는 피보나치 수를 DP로 구하기가 떠오르는 문제였습니다.

 

탑다운 방식으로 DP를 해결하는 방식인데, 이 문제 역시 문제 풀이의 로직만 생각해낸다면 구현은 탑다운으로 거의 똑같이 할 수 있는 것 같습니다.

 

이 문제가 DP의 정당성을 가지는 이유(부분 최적해가 전체 최적해를 보장하는 이유)는 각 자릿수가 하나라도 다르면 다른 경우의 수로 취급하기 때문이입니다. 예를 들어 어떤 수 N을 3개의 숫자로 표현한다고 해보죠.

 

N = 0 + _ _

N = 1 + _ _ 

N = 2 + _ _

...

N = (N-1) + _ _ 

 

이 때, 위의 모든 경우의 수는 서로 다른 경우임이 자명하고, 위의 경우의 수들을 모두 더하면 전체 경우의 수가 됩니다.

 

따라서, 이 문제의 로직(점화식)은 아래와 같이 세울 수 있고 이를 코드로 구현하면 정답을 받을 수 있습니다.

 

# dp[i][j] = _ _ _ _ _ ... _ _ j개의 수로 i를 만드는 경우의 수

# dp[i][j] = 맨 앞에 0이 오는 경우, 1이 오는 경우,..., i-1, i가 오는 경우

# --> dp[i][j] = dp[i][j-1] + dp[i-1][j-1] + dp[i-2][j-1] + .... + dp[1][j-1] + dp[0][j-1]

# --> dp[i][j-1] = dp[i][j-2] + dp[i-1][j-2] + dp[i-2][j-2] + .... + dp[1][j-2] + dp[0][j-2]

# ...

 

[풀이]

def recursivelySolve(i, j):
    if j == 1:
        return dp[i][j]
    else:
        for x in range(i+1):
            dp[i][j] += dp[i-x][j-1]

n, k = map(int, input().split())

dp = [[0] * 201 for _ in range(201)]
for i in range(1,201):
    dp[i][1] = 1

for i in range(201):
    for j in range(1, 201):
        recursivelySolve(i,j)
print(dp[n+1][k] % 1000000000)