부분의 최댓값이 제한된 분할
골드 V의견: 0
자연수 \(N\) 과 \(M\) 이 주어진다. \(N\) 을 자연수들의 합으로 분할하되, 각 부분(더해지는 수)이 모두 \(M\) 이하인 분할의 서로 다른 경우의 수를 구하여라. 더하는 순서만 다른 것은 같은 분할로 본다.
예를 들어 \(N = 6\), \(M = 3\) 인 경우 가장 큰 수가 \(3\) 을 넘지 않는 분할은 \(3+3 = 3+2+1 = 3+1+1+1 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1\) 의 \(7\) 가지다.
\(1 \le M \le N \le 2000\)
첫째 줄에 두 자연수 \(N\) 과 \(M\) 이 공백으로 구분되어 주어진다 (\(1 \le M \le N\)).
모든 부분이 \(M\) 이하인 \(N\) 의 분할 방법의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 첫째 줄에 출력한다.
6 3
7
모든 부분이 \(3\) 이하인 \(6\) 의 분할은 \(3+3 = 3+2+1 = 3+1+1+1 = 2+2+2 = 2+2+1+1 = 2+1+1+1+1 = 1+1+1+1+1+1\) 의 \(7\) 가지다.
5 1
1
모든 부분이 \(1\) 이하이면 \(1+1+1+1+1\) 뿐이므로 \(1\) 가지.
5 5
7
\(M = 5 \ge N\) 이면 제한이 없으므로 \(5\) 의 일반 분할 수 \(7\) 과 같다.
골드 IVriseoj 작성
출처 Original
평가 및 의견
부분의 최댓값이 제한된 분할
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
부분의 최댓값이 제한된 분할