[BOJ] 2225번 - 합분해

---

문제설명

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

2225번: 합분해

사고과정

• 0~N까지 수 중에서 K개를 아무거나 뽑아서 합이 N이 되는 경우의 수를 모두 구하는 것이었다. 2차원 리스트 DP 테이블을 운영해야 하는 느낌이 들어서 시도해보았더니 맞는 풀이였다!
• DP 테이블의 행($i$)는 N을, 열($j$)는 K로 하고 원소값을 몇 가지 예시로 연습장에 구현해보면 특정한 규칙이 발생한다는 것을 포착할 수 있었다. 이 때, DP 테이블에서 N=1일 때는 K가 어떤 값이냐에 따라 K개가 되었다. 반대로 K=1일 때는 N이 무엇이던 간에 모두 1개임을 알 수 있다. 따라서 초기 DP 테이블 값에 이를 반영해주고 다른 위치들의 값들은 바로 왼쪽값과 바로 위쪽값의 합임을 알 수 있다. 따라서 점화식은 다음과 같았다. $dp[i][j] = dp[i][j-1] + dp[i-1][j]$
• 참고로 시간 제한은 2초로 여유로운 편이였다. 초기 DP 테이블을 갱신하는데, 최대 데이터 범위가 N, K 모두 200이었기 때문에 최악의 경우 총 400번의 연산이 수행된다. 그리고 DP를 수행하면서 2중 루프를 도는데 최악의 경우 200 곱하기 200인 4만번을 수행하기 때문에 총 4만 200번 연산이 최악에 수행된다. 따라서 시간 내에 여유롭게 통과된다!
• 마지막에 10억으로 나눈 나머지 값을 출력하는 부분도 잊지 말자!

풀이

n, k = map(int, input().split())
mod = int(1e9)
dp = [[0] * (k+1) for _ in range(n+1)]
# 총 최악 400번 연산 수행
for j in range(1, k+1):
    dp[1][j] = j
for i in range(1, n+1):
    dp[i][1] = 1
# 시간복잡도 4만번 수행
for i in range(2, n+1):
    for j in range(2, k+1):
        dp[i][j] = dp[i][j-1] + dp[i-1][j]

print(dp[n][k] % mod)