레이팅 미적용설명
자연수 \(N\) 과 \(K\) 가 주어진다. \(N\) 을 정확히 \(K\) 개의 자연수(각각 \(1\) 이상)의 합으로 분할하는 서로 다른 경우의 수를 구하여라. 더하는 순서만 다른 것은 같은 분할로 본다.
예를 들어 \(N = 7\), \(K = 3\) 인 경우 \(5+1+1 = 4+2+1 = 3+3+1 = 3+2+2\) 의 \(4\) 가지가 있다.
제약
\(1 \le K \le N \le 2000\)
입력 형식
첫째 줄에 두 자연수 \(N\) 과 \(K\) 가 공백으로 구분되어 주어진다 (\(1 \le K \le N\)).
출력 형식
\(N\) 을 정확히 \(K\) 개의 자연수 합으로 분할하는 방법의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 첫째 줄에 출력한다.
예제 1
입력
7 3
출력
4
설명
\(7\) 을 정확히 \(3\) 개의 자연수 합으로 나타내면 \(5+1+1 = 4+2+1 = 3+3+1 = 3+2+2\) 의 \(4\) 가지다.
예제 2
입력
5 1
출력
1
설명
부분이 하나뿐이면 \(5\) 자기 자신뿐이므로 \(1\) 가지.
예제 3
입력
5 5
출력
1
설명
\(5\) 개의 부분으로 나누는 방법은 \(1+1+1+1+1\) 뿐이므로 \(1\) 가지.
문제 시리즈
문제 정보
riseoj 작성
출처 Original
태그