[Python] BOJ / 2225번 / 합분해

2225번: 합분해

 

📝 문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

 

📜 풀이

• 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수는 아래와 같은 규칙으로 구할 수 있을 것이다.
  
  • dp[k][n]을 정수 k개를 더해서 그 합이 n이 되는 경우의 수라고 할 때
  • dp[k][n] = dp[k - 1][0] + dp[k - 1][1] + dp[k - 1][2] + ... + dp[k - 1][n - 1] + dp[k - 1][n]
• 위 식이 성립되는 이유를 설명하자면 다음과 같다.
  
  • n = 2이고 k = 3인 경우를 예로 들어보자
  • 즉, 정수 3개를 더해서 그 합이 2가 되도록 하는 경우의 수를 구한다고 가정하면 아래와 같은 방법을 생각해볼 수 있다.
    • 정수 2개를 더해서 그 합이 0이 되는 경우의 수(0 + 0)에 추가로 2만 더해준다면, 정수 3개를 더해서 그 합이 2가 되는 경우가 된다.(0 + 0 + 2)
    • 정수 2개를 더해서 그 합이 1이 되는 경우의 수(0 + 1, 1 + 0)에 추가로 1만 더해준다면, 정수 3개를 더해서 그 합이 2가 되는 경우가 된다.(0 + 1 + 1, 1 + 0 + 1)
    • 정수 2개를 더해서 그 합이 2가 되는 경우의 수(0 + 2, 2 + 0, 1 + 1)에 추가로 0만 더해준다면, 정수 3개를 더해서 그 합이 2가 되는 경우가 된다.(0 + 2 + 0, 2 + 0 + 0, 1 + 1 + 0)
  • 즉, 이 예시에서는 위 3가지 상황에서의 경우의 수를 모두 더해주기만 하면 원하는 결과를 얻을 수 있는 것이다.
• 다만 위의 점화식으로 구현할 경우 문제를 통과하는 데에는 문제없지만 3중 반복문을 사용하게 되어 시간이 조금 걸리게 된다.
• 시간 복잡도를 조금 더 낮추기 위해서는 다음과 같은 점화식으로 변경해줄 수 있다.
  • dp[k][n] = dp[k - 1][n] + dp[k][n - 1]
• 어째서 위와 같은 점화식으로 바꿀 수 있는지는 아래 표를 보면 쉽게 이해할 수 있다.

N / K	N = 0	N = 1	N = 2
K = 1	0	1	2
K = 2	00	01, 10	02, 11, 20
K = 3	000	001, 010, 100	002, 011, 101, 020, 110, 200

• dp[3][2]를 구한다고 가정했을 때, 우리는 굳이 이전 행으로 돌아가 반복문을 돌며 경우의 수를 일일이 더해줄 필요 없다.
• 그 이유는 애초에 dp[k][n - 1] 즉, dp[3][1]이 dp[2][0]과 dp[2][1]의 합으로 구해진 경우의 수이기 때문이다.
• 즉, dp[2][0]과 dp[2][1]은 따로 신경 쓸 필요가 없으며, dp[3][1]에 나머지 dp[2][2]만 더해주면 되는 것이다.
  • dp[3][2] = dp[3][1](dp[2][0] + dp[2][1]) + dp[2][2]

 

💻 소스코드

# dp[k][n] = dp[k - 1][0] + dp[k - 1][1] + dp[k - 1][2] + ... + dp[k - 1][n - 1] + dp[k - 1][n]

MOD = 1000000000
n, k = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(k + 1)]
dp[1] = [1] * (n + 1)

for i in range(2, k + 1):
    for j in range(n + 1):
        for l in range(j + 1):
            dp[i][j] += dp[i - 1][l]
        dp[i][j] %= MOD
print(dp[k][n])

# dp[k][n] = dp[k - 1][n] + dp[k][n - 1]

MOD = 1000000000
n, k = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(k + 1)]
dp[1] = [1] * (n + 1)

for i in range(2, k + 1):
    for j in range(n + 1):
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        dp[i][j] %= MOD

print(dp[k][n])