[백준 17213번] 과일 서리 (C++)

문제링크 : https://www.acmicpc.net/problem/17213

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

ll N, M;
ll dp[31][31];

void func()
{
    dp[0][0]=1; //첫 번째 값 1
    for(int i=1; i<31; i++)
    {
        dp[i][0]=1; //좌측 값 1
        for(int j=1; j<=i; j++)
        {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; //파스칼 삼각형 공식
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;

    func();

    cout << dp[M-1][M-N]; //N+M-N-1 = M-1, r = M-N
    return 0;
}

 

중복 조합 문제이다.

간단하게 생각해보면 nHm 이지만, 모든 종류의 과일이 적어도 1개씩 있어야 한다는 조건 때문에 nHm-n이 된다.

이를 조합으로 변환하여 계산을 해주면 된다.

그러면 nCr = n+r-1Cr = n+m-n+1Cm-n이 된다.

해당 계산은 파스칼 삼각형 공식을 통해 dp 형태로 구할 수 있다.

파스칼 삼각형 공식 : nCr = n-1Cr-1 + n-1Cr

​

파스칼 삼각형의 경우 맨 첫 번째 값과, 맨 좌측 값이 전부 1이여야 하므로 해당 값들을 1로 초기화 후 계산을 진행해준다.

이후 n과 r에 해당하는 위치의 dp 배열 값을 출력해주면 된다.

​