이 포스팅은 다시 풀 문제들 시리즈 5 편 중 4 번째 글 입니다.

  • Part 1 - 25: 길 찾기 게임
  • Part 2 - 백준(1520번): 내리막 길
  • Part 3 - 백준(1937번): 욕심쟁이 판다
  • Part 4 - This Post
  • Part 5 - 백준(2812번): 크게 만들기
▼ 목록 보기

목차

▼ 내리기

골드5 : 동적계획법 문제이다.

풀이

잘 접근했다고 생각했는데, 점화식을 잘 못 구했다. 나중에 다시 제대로 이해하고 적을 것

Code

from pprint import pprint

n, k = map(int, input().split())
dp = [[0 for _ in range(n + 1)] for _ in range(k + 1)]
mod = int(1e9)
for i in range(n + 1):
    dp[1][i] = 1


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

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

Reference