2225번 합분해

문제 출처 : https://www.acmicpc.net/problem/2225

사고과정

조건들에 대해 집중해서 생각해봤다.
조건1. 결국 모든 경우의 수는 합이 N
조건2. 0이 들어가더라도 상관X. 결국 K개의 자리에서 순서 고려
조건3. 한 개의 수가 여러 번 사용 가능

이 세 가지를 중점적으로 생각하면 문제를 해결하려 했다. 일단 N=6, K=4라는 예시에서 모두 나열하며 규칙을 찾아보려 했다. 0을 고려하게 되므로 K=1일 때, K=2일 때... 아니면 첫번째 수에 따라 나열해보기도 하고... 하지만 이렇게 나열을 해서 결국 조건에 맞는 조합을 찾는다(1)고 해도 그 조합에서 중복되는 게 있는지, 어떤 수가 몇 번 중복되는지(2) 이런 번거로운 작업을 거치게 되니 이 방법으로 힘들겠다는 생각이 들었다. 그래서 해답을 보면 결국 정해진 N,K 내에서 나오는 조합들로만 해결할 수 있는 부분이 아니었다.

N과 K의 관계에서 조망하고 넓은 규모의 관점에서 바라봤어야 문제가 해결 가능한 것이다. ( 2차원 DP )

-> 직관적으로 이해할 수 있을까

import sys

N, K = list(map(int,sys.stdin.readline().rstrip("\n").split()))

dp = [[0 for n in range(N+1)] for k in range(K+1)]

for n in range(1,N+1) :
    dp[1][n] = 1
for k in range(1,K+1) :
    dp[k][1] = k
for n in range(2,N+1) :
    
    for k in range(2,K+1) :
        dp[k][n] = dp[k-1][n]+dp[k][n-1]
        
print(dp)

우리는 부분을 보고 전체를 이해하기는 힘들 것이다. 하지만 전체를 볼 수 있다면 그 안의 부분을 볼 수 있을 것이고 전체를 보며 부분들의 규칙을 이해할 수 있다면 전체를 이해하기도 수월할 것이다.