합분해
BOJ 2225 합분해
boj 2225 합분해 - 문제 링크 https://www.acmicpc.net/problem/2225 - 문제 해설 테이블 D[i][j]를 n이 i이고 k가 j일 때의 경우의 수라고 정의한다. 경우의 수를 어떻게 나눌지 잘 떠오르지 않아서 일단 n과 k에 따른 경우의 수를 작은 수부터 나열해보았다. 표로 나열해보면서 점화식을 유추해보자. 예를 들어 D[3][3]을 구한다고 해보자. 3을 3가지 수의 합으로 나타내는 경우는 0부터 3까지의 수를 2가지 수의 합으로 나타낸 것에다가 3이 되기위해 필요한 수를 더하면 된다. 0을 2가지 수의 합으로 나타낸 경우 : (0 + 0) 1을 2가지 수의 합으로 나타낸 경우 : (0 + 1), (1 + 0) 2를 2가지 수의 합으로 나타낸 경우 : (0 + 2), (..