백준 2225 합분해 (파이썬)

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

import sys
def solve():
    arr = [[0] *(N+1) for i in range(K+1)]
    for i in range(1, K+1):
        for j in range(1, N+1):
            if j == 1:
                arr[i][j] = i
            elif i == 1:
                arr[i][j] = 1
            else:
                arr[i][j] = arr[i-1][j] + arr[i][j-1]

    return arr[K][N]
if __name__ == "__main__":
    input = sys.stdin.readline
    N, K = map(int, input().split())

    print(solve()%1000000000)

arr의 행은 K(정수의 개수)를 의미하고 열은 N(정수 N)을 의미합니다

 

첫 행은 1로 초기화 시킵니다. 이유는 정수 N을 1개를 선택하는 경우의 수는 1개만 있기 때문입니다.

 

1열은 행으로 초기화 시킵니다. 이유는 1을 K개로 만드는 경우는 

(1),

(0,1), (1,0)

(0,0,1), (0,1,0), (1,0,0) 

...

위 처럼 행과 같아지기 때문입니다.

 

규칙성을 찾아본 결과 i,j의 값은 [i-1][j] + [i][j-1] (왼쪽, 위쪽) 값을 합한 값을 넣습니다.

 

결과 및 정리

도저히 답을 찾지 못해 검색을 해서 답을 해결했습니다.

여러가지 방법이 있었지만 저는 위 방법이 가장 저에게 잘 맞는 것 같아 해결했습니다. 

여러가지 문제를 풀고있지만 DP 유형의 문제가 저에겐 가장 어려운 유형 중 하나인 것 같습니다.