백준 27715, 우표 구매하기 (Easy)

개요

문제 링크
골드 4, 조합론
1, 2원짜리 우표를 중복을 허용하여 선택해 K원 구성하기

---

접근

1. 대표적인 중복조합 문제, K를 1, 2의 단위로 쪼개보자. 2원짜리를 i개 쓴다고 하면 K = (i×2) + (K-i×2)가 되는데,
2. 2원짜리를 i개 고르는 방법은 M개의 2원짜리 동전 {q1, q2, ... qM}에서 아래의 식을 구성하는 방법의 수이다.
   q1+q2+...+qM = i
3. 나머지 1원짜리를 K-i×2개만큼 고르는 방법도 마찬가지로 적용할 수 있다. N개의 1원짜리 동전 {p1,p2, ... pN}의 개수의 합이 K-2×i가 되면서 각 동전별 구분이 없고 중복을 허용하므로 아래와 같이 표현할 수 있다.
   p1+p2+...+pN = K-2*i
4. 나머지는 수능 확통을 복습해보자. 위와 같은 식이 주어지고 모든 원소가 0이상이면 중복조합으로 표현할 수 있다. 중복을 허용한다 안한다 말로 표현하는 것보다 저 식 하나면 중복조합 문제가 된다. 마치 NP-complete같은 존재이다.
5. nHk = (n+k-1)Ck이고, nCk = (n-1)Ck + (n-1)C(k-1) 이므로 미리 combination배열을 만들어 사용하자.

우표구매하기 Hard는 뤼카정리와 생성함수를 사용하는데 생성함수를 배운지 너무 오래돼서 복습을 후딱 끝내고 도전해려고 한다.

---

Pseudo code

H(n,k) {
    return C[n+k-1][k]
}
C[0][0]=1; // 0C0 = 1
for (i = 1~N)
    C[i][0] = C[i][i] = 1
    for (j = 1~i-1)
        C[i][j] = C[i-1][j]+C[i-1][j-1]
for (i=0, i*2<=k, i++)
    s += H(n,k-i*2) * H(m,i)
    // 1이 k-i*2개, 2가 i개

---

Source code

#include <bits/stdc++.h>
using namespace std;

#define N 2010
using ld=long long;
ld n,m,k,p,C[N][N];
ld H(ld n,ld k) {
    n=n+k-1;
    if (n<0) return 1;
    return C[n][k];
}
int main() {
    cin>>n>>m>>k>>p;
    C[0][0]=1;
    for (ld i=1;i<N;i++) {
        C[i][0]=C[i][i]=1;
        for (ld j=1;j<i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
    }
    ld s=0;
    for (ld i=0;i*2<=k;i++)
        s=(s+(H(n,k-i*2)*H(m,i))%p)%p;
    cout<<s;
}