[백준] 2225 '합분해' 파이썬(python)

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

2225번: 합분해

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

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

Point

• 갯수를 구하는 것이기에 갯수에 대한 규칙을 찾는 것이 중요

  K \ N	1	2	3	4
  1	1	1	1	1
  2	2	3	4	5
  3	3	6	10	15

• 갯수들을 도표로 해서 확인해 보면 규칙이 dp[i][j] = dp[i-1][j] + dp[i][j-1] 인 것을 확인할 수 있다.
• dp테이블을 만들고, 규칙을 찾아 점화식을 만들면 끝나는 문제