백준 - 합분해(2225)
Dynamic Programming
문제
0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.
덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.
입력
첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.
출력
첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.
import sys
n, k = map(int, sys.stdin.readline().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])
굉장히 방대한 조합 문제라고 생각했다.
DP가 약점이 된 이유는 케이스를 너무 크게 확장하는 것.
DP는 곧 점화식, 점화식은 규모가 작은 케이스부터 시작.
참고)
https://it-garden.tistory.com/341
Author And Source
이 문제에 관하여(백준 - 합분해(2225)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@skkfea07/백준-합분해2225저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)