7107 : 분할수 (정수 분할)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
자연수 n이 주어졌을 때, n을 여러 자연수의 합으로 나타내는 경우의 수(순서가 없는 분할 수, P(n))를 구하십시오.
예를 들어, 4의 분할 수는 4, 3+1, 2+2, 2+1+1, 1+1+1+1 로 총 5가지입니다.
예를 들어, 4의 분할 수는 4, 3+1, 2+2, 2+1+1, 1+1+1+1 로 총 5가지입니다.
입력 설명
첫째 줄에 자연수 $n$이 주어집니다. ($1 \le n \le 200$)
출력 설명
$n$의 분할수를 $10^9+7$로 나눈 나머지를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7도움
동전 1, 2, ..., n원을 써서 n원을 만드는 경우의 수와 완벽히 동일한 DP 방식으로 해결할 수 있습니다.