백준 2225번 합분해 문제풀이 c++

https://www.acmicpc.net/problem/2225

2225번: 합분해

문제해석

 

숫자를 중복해서 사용가능하고 k개를 사용해서 합이 n이되게하면 되는 문제이다

즉 a1+a2+a3+...+ak=n 를 만족하는 경우의 수를 세면되는데

이 문제는 고등학교때 확률과 통계 순열 조합 파트에서 많이 접했던 문제중 하나이기 때문에 

고등학교 수업을 잘 들었으면 쉽게 풀 수있는 문제라고 생각했는데

지금은 수능수학이 선택과목이라 확통러가 아니라면 모를지도 모르겠다.

 

a1+a2+a3+...+ak=n을 만족하는 0이상의 정수의 조합 개수를 세면

kHn이고 이는 k+n-1Cn이다.

즉 nCr을 구하는 문제이기때문에 다이나믹프로그래밍으로 파스칼 삼각형을 만들고 단순 출력하면 끝.

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int a[405][405];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
    for(int i=0; i<405; i++)
    {
        a[i][0]=1;
    }
    for(int i=1; i<405; i++)
    {
        for(int j=1; j<=i; j++)
        {
            a[i][j]=(a[i-1][j-1]+a[i-1][j])%1000000000;
        }
    }
    cout<<a[n+k-1][n];
}