[백준] 2225 합분해 - 파이썬 [골드5]

이번에 소마 코딩테스트를 준비하면서 골드문제를 풀어보았는데, 헷갈리는점이 많아 정리한다.

---

문제

백준 합분해 2225

---

풀이

DP 문제로 분류되어있지만, DFS로도 풀수있지 않을까 라는 생각이 들었지만 아주 바보같은 생각이었다. ㅎㅎ

아무튼 풀이를 해보자.

예제 1을 보면, 20을 0~20까지의 정수 2개를 더하여  20을 만들수있는경우의수를 도출한다.

케이스별로 경우의수를 정리해보면 아래와 같다.

	N =1	N = 2	N = 3	N = 4	N =5	N =6
K = 1	1	1	1	1	1	1
K = 2	2	3	4	5	6	7
K = 3	3	6	10	15	21	28
K= 4	4	10	20	35	56	84

N = 2 이고 K = 2인 경우는 N = 2 이고 K= 1 인것과 N = 1이고 K = 2인것을 더한값과 같다는것을 확인할 수 있다.
이것을 점화식으로 표현한다면 

DP[A][B] = DP[A - 1][B] + DP[A][B-1]

위와 같은 식으로 정리할 수 있다.
하지만, 이것을 코드로 풀어내는데 나는 애를 썼다. 헷갈렸기때문에 ....ㅎㅎㅎ
아무튼 아래의 코드로 풀이했다.

import sys

input = sys.stdin.readline

N, K = map(int, input().split())

dp = [[0] * N for _ in range(K)]

for i in range(N):  # N = 1 인경우는 모두 1
    dp[0][i] = 1

for i in range(K):  # N = 1인 값은 자릿수에 따라 경우의수가 1씩 증가
    dp[i][0] = i + 1

for i in range(1, K):  # 실제 식
    for j in range(1, N):
        dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000

print(dp[K - 1][N - 1])

• K = 1 인 경우에는 N이 어떤수던 모두 하나의 경우의수를 가진다. 
  • 예 )  N=3,K=1 은 한자리로 3을 만들수있는건 오직 3 뿐
• N = 1인 경우에는 K가 어떤 값이던 1씩 증가한다.

초기화 과정 결과

위 처럼 2차원배열을 초기화 시킨후, dp[1][1]부터 로직을 진행했다.

아주 손쉽게(?) SOLVE