Search

[백준 2225] 합분해

[백준 2225] 합분해

Tip

n = 1일 경우, 경우의 수는 k
k = 1일 경우, 경우의 수는 자기자신 1
k = 2일 경우, 경우의 수는 n + 1
k, n이 2 이상인 경우, d[k][n] = d[k][n - 1] + d[k - 1][n]

풀이 소스 코드

import sys si = sys.stdin.readline # n, k 입력 n, k = map(int, si().split()) # DP 테이블 d = [[0] * 201 for i in range(201)] for i in range(201): d[1][i] = 1 d[2][i] = i + 1 for i in range(2, 201): d[i][1] = i for j in range(2, 201): d[i][j] = (d[i][j - 1] + d[i - 1][j]) % 1000000000 print(d[k][n])
Python