백준[ 2225 | Python ] 합분해

문제

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

풀이

먼저 n까지의 숫자를 k개로 만드는 경우의 수를 따저보아야 한다.
경우의 수를 표로 나타내면 아래와 같이 나온다.

또 위의 표를 통해서 규칙을 찾아낼 수 있는데,
n이 2보다 큰 이후로는이전 행의 같은 열의 값과 이전 열의 같은 행의 값을 더해주면 원하는 값이 나온다는 것이다.
(파란 선을 보면 쉽게 이해된다.)
이를 토대로 dp테이블에 n크기의 행렬 k개를 만들어준다.

이후로 발견한 규칙이 n이 3이상일 때 부터 보이기 때문에 dp[1](k가 1인 경우)에는 n일 경우 1을 가지는 규칙을 적용해 값을 넣어주고 dp[2](k가 2인 경우)에는 k일 경우 k+1을 가지는 규칙을 적용해 값을 넣어준다.

이후로 앞서 말한 규칙을 적용해 구현한다.

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

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

생각 & 정리

사소한 부분을 넘어갔다가 너무 많은 시간이 걸렸다.
사실 지금까지 dp문제를 풀면서 결과를 어떤 수로 나누어 출력하라는 문제를 많이 보았는데,
아직까지 과정 중간에 나눠줘야 하는 이유를 잘 모르겠다.
골드 문제로 넘어온지 얼마 안됐는데, 생각보다는 풀려서 자신감이 좀 생긴 것 같다.