Python3,DP
문제
입출력
입출력 예시
주요 포인트
n이 1이면 k가 어떤 수가 오든 경우의 수는 k이다.
k = 1, n = 2일 때, (1, 0), (2, 0) => 2개
k = 1, n = 4일 때, (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0), (0, 0, 0, 1) => 4개
k = 2일 때,
n이 20이라면 경우의 수는 21개이다.
-> (10, 10) 1개
(0, 20), (1, 19), (2, 18), (3, 17), (4, 16), (5, 15), (6, 14), (7, 13), (8, 12), (9, 11) 총 10개. 순서 바꾼 거 합치면 20개.
n이 3이라면 경우의 수는 4개이다.
-> (0, 3), (1, 2), (2, 1), (3, 0)
즉, k = 2일 때, 경우의 수는 n+1개이다.
k = 3일 때,
n이 2라면, (0, 1, 1), (1, 0, 1), (1, 1, 0), (0, 0, 2), (0, 2, 0), (2, 0, 0) 총 6개이다.
n이 3이라면, (1, 1, 1), (0, 1, 2), (0, 2, 1), (1, 0, 2), (2, 0, 1), (1, 2, 0), (2, 1, 0), (0, 0, 3), (0, 3, 0), (3, 0, 0) 총 10개이다.
표로 나타내면
출처: https://it-garden.tistory.com/341
dp[i][j] = dp[i][j-1] + dp[i-1][j] 이다.
최종 코드
n, k = map(int, input().split())
dp = [[0]*201 for i in range(201)]
for i in range(201):
dp[1][i] = 1
dp[2][i] = i+1
for i in range(2, 201):
dp[i][1] = i
for j in range(2, 201):
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 1000000000
print(dp[k][n])피드백
n과 k의 관계에 대해서 먼저 생각하고 규칙을 하나씩 봐야 하는 문제였다. 쉽게 셀 수 있는 작은 수부터 계산하고 앞뒤, 대각선 관계를 살펴봐야 한다.
