[백준] 17213 과일 서리

17213번: 과일 서리

 

www.acmicpc.net

풀이

중복 조합을 사용해서 해결하면 된다. 이 때 중요한 것은 모든 과일의 종류가 최소한 1개는 포함되어야한다는 점이다. 이를 조심해서 구현하면 된다. 조합을 구현할 때는 동적 계획법을 사용해서 구현했다.

코드

#include <iostream>
using namespace std;

int n, m;
int comb[41][41];

int combination(int a, int b) {
    int& ret = comb[a][b];
    if (ret != -1) return ret;
    if (b == 0 || a == b) return ret = 1;
    return ret = combination(a - 1, b - 1) + combination(a - 1, b);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    cin >> m;
    for (int i = 1; i <= 40; i++) for (int j = 0; j <= 40; j++) comb[i][j] = -1;
    cout << combination(m - 1, m - n) << '\n';
    return 0;
}