[Python] 백준 2225번: 합분해 풀이

 

 

소스코드

n, k = map(int,input().split())
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(0, n+1):
    for j in range(1, k+1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][k] % 1000000000)

 

만약 n=20, k=5 라면

20을 5개로 나눈 것은 [0+(20을 4개로 나눈것)] + [1+(19를 4개로 나눈것)] + ... + [19+(1을 4개로 나눈것)] + [20+(0을 4개로 나눈것)] 일 것이다.

 

즉 점화식으로 표현한다면, dp[n][k] = dp[0][k-1] + dp[1][k-1] + ... dp[n-1][k-1] + dp[n][k-1] 일 것이다.

 

그런데 이 점화식을 이용한다면 for문을 3개 이용해야 한다. 그래서 좀 더 간결화 할 수 있는 방법을 생각해보니,

dp[n-1][k] = dp[0][k-1] + dp[1][k-1] + ... dp[n-1][k-1] 임을 이용할 수 있겠다 생각이 싶었다.

 

따라서 dp[n][k] = dp[n-1][k] + dp[n][k-1] 으로 표현할 수 있다.

 

 

 

별도로, 파이썬에서 음수 인덱스를 지정하면 인덱스 에러가 나는 것이 아니라 뒤에서부터 접근하는 것을 알고는 있었다.

그러나 다차원 배열에서도 똑같이 적용되는가 의문이 들어 (위의 dp[0][1] = dp[-1][1] + dp[0][0] 이므로)

테스트를 해본 결과 ,,

이렇게 똑같이 뒤에서부터 접근함을 알 수 있었다.