백준 2225: 합분해

합분해 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

29222

12756

9227

42.059%

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 복사

20 2

예제 출력 1 복사

21

예제 입력 2 복사

6 4

예제 출력 2 복사

84

출처

• 잘못된 데이터를 찾은 사람: tncks0121

알고리즘 분류

• 수학
• 다이나믹 프로그래밍

음 백준 11057 오르막수 문제랑 점화식이 똑같다 . 그래서 설명은 생략하겠다.

코드

#include<iostream>
#include<vector>

using namespace std;

int dp[100];

int main() {
int n, k;
cin >> n  >> k ;

for (int i = 0; i <= n; i++)
dp[i] = 1;

for (int i = 2; i <= k; i++) {
for (int j = 1; j <= n; j++) {
dp[j] = (dp[j] + dp[j - 1])%1000000000;
}
}
cout << dp[n];
return 0;
}