2225 합분해 파이썬 백준

문제)

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

2225번: 합분해

 

 

dp를 만들때 2차원 배열로 만들었다.

dp[i][j] 일때, i는 바텀업 방식으로 만들어진 합이고, j는 그 합을 만드는데 사용한 정수의 개수이다.

난 문제풀때 보면 문제의 간단한 예시를 가지고 그걸 바탕으로 알고리즘을 만들어 나가는 것 같다.

이번 문제도 그렇다. 

dp[4][2]와 dp[4][3]이 올바른 값을 가질려면 어떤 값들이 더해져야 하는지 생각했다.

 

dp 배열의 인덱스는 하나의 목적을 가지고 있고, 그 목적은 문제의 답과 관련이 있다.

문제를 단순화했을 때 키워드는 합, 사용하는 정수의 개수

주의할 점은 순서가 다른 경우는 다른 경우로 세는 것.

dp는 이전 단계에 대해 생각해 보는게 좋은듯

 

1. 입력 받기

2. dp 생성과 초기화

3. dp 바텀업

어떤 정수 하나를 더해 그 합이 되도록 해야하니 [j] 자리가 -1 돼 있는 값들이 더해져야 함

합이 되는 경우의 수는 0부터 i까지의 dp들을 다 더하는 경우가 됨

4. 답 출력

 

소스코드)

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

dp = [[0] * (k+1) for _ in range(n+1)]
# dp[i][j] : i는 합, j는 합을 만드는데 사용한 정수

for i in range(0, n+1):
    dp[i][1] = 1

# dp[4][2] = dp[4][1] + dp[3][1] + dp[2][1] + dp[1][1] + dp[0][1]
# dp[4][3] = dp[4][2] + dp[3][2] + dp[2][2] + dp[1][2] + dp[0][2]

for p in range(2, k+1):
    for i in range(0, n+1):
        for j in range(0, i+1):
            dp[i][p] += dp[j][p-1]
            #dp[i][p] += dp[i-j][p-1] + 1


print(dp[n][k] % 1000000000)