[Python/백준] 2225 합분해

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

2225번: 합분해

<문제 해설>

다이나믹 프로그래밍 문제이다. 문제의 포인트는 덧셈의 순서가 바뀐 경우 다른경우로 센다는 것과 0부터 N까지의 정수라는걸 기억해야한다. 가령 숫자 2를 2가지 정수를 더해서 만들때 0+2, 1+1, 2+0 이런식으로 3개의 경우가 생기는 것이다.

이문제는 이런 결과를 저장해 나가는 방식으로 하면된다. 0부터 N까지의 정수를 1부터 k개를 더해서 나오는 경우의 수를 다 저장하면된다. 그후 배열의 가장 뒤에있는 숫자를 출력해주면 된다. 자세한것은 예시를 들어서 설명하겠다.

<예시>

다음은 문제 예제 입력 2로나와있는 N = 6 K = 4일경우의 가짓수를 모두 표로 나타냈다. 본표는 0부터 6을 정수 k개를 사용할대 만들수 있는 가짓수이다. 왜 이런 결과값이 나타나는지 확인해보자.

이번 표는 가짓수를 모두 적어놨다. 여가서 규칙을 찾아볼수 있는데 0을 만드는 가짓수는 항상 1이다. 2을 만드는 k개수의 가짓수는 k-1개수의 0+1+2드르이 가짓수를 모두 더한 값이다. 표를 보면 앞에있는 비슷한 숫자로 가짓수가 다시 생기는 걸 볼수 있다. 만약 정수 n을 k개 더해서 만드는 경우의 수는 k-1개 더해서 만드는 0~n까지의 가짓수를 다 더해주면된다.

빨간색 칸에 적힌 수를 구하기 위해선 빨간색 숫자들을 모두 더해주면되고, 주황색 칸에 적힌 수를 구하기 위해선 주황색 숫자들을 모두 더해주면 되는 방식이다.  이런 방식으로 숫자들을 구해준후 배열의 마지막 숫자를 출력해주면 답이 된다.

<코드>

import sys
N, K = list(map(int,sys.stdin.readline().split()))

dp = []
dp.append([1]*(N+1))
for j  in range(K-1):
    dp.append([1] + [0 for i in range(N)])

for i in range(1,K):
    for j in range(1,N+1):
        for m in range(j+1):
            dp[i][j] += dp[i-1][m]
            
print(dp[-1][-1]%1000000000)

<코드 설명>

import sys //sys라이브러리 불러오는 import
N, K = list(map(int,sys.stdin.readline().split())) //N, K값 정수로 받아오기

dp = [] //가짓수 저장할 배열 생성
dp.append([1]*(N+1)) //어떤 숫자를 1가지 숫자만 사용해서 만드는 법은 1가지밖에 없으니 초기배열은 1로 설정
for j  in range(K-1): //K-1번 만큼 반복하면서
    dp.append([1] + [0 for i in range(N)]) //나머지 배열의 0을 만드는 방법만 1로 나머지는 값을 더해줄꺼니 0으로

for i in range(1,K): //1가지 숫자만 사용하는 법은 1로 설정햇으니 2가지 숫자 사용하는 법부터 시작
    for j in range(1,N+1): //배열의 1~N까지 숫자들을 불러오기
        for m in range(j+1): //불러운 숫자만큼 반복하면서
            dp[i][j] += dp[i-1][m] //앞배열의 숫자보다 작거나 같은 숫자의 가짓수를 모두 더해주기
             
print(dp[-1][-1]%1000000000) //가장 뒤에있는 수를 출력하면서 문제조건으로 나눈 나머지를 출력하