백준 2293번 : 동전 1

• 분류: 다이나믹 프로그래밍

코드(방법 1)

#include <iostream>
using namespace std;

int n, k;
int v[101];
int table[10001] = {0, };

int main() {
    cin >> n >> k;
    for(int i=1 ; i<=n ; i++) {
        cin >> v[i];
    }
    for(int i=0 ; i<=k ; i++) {
        table[i]= i%v[1]==0 ? 1 : 0;
    }
    for(int nn=2 ; nn<=n ; nn++) {
        int temp[10001] = {0, };

        for(int i=0 ; i<=k ; i++) {
            for(int j=i ; j>=0 ; j-=v[nn]) {
                temp[i] += table[j];
            }
        }
        for(int i=1 ; i<=k ; i++) {
            table[i] = temp[i];
        }
    }
    cout << table[k];
}

• 코멘트
  
  공간 제한이 4MB밖에 없기 때문에 n*k, 즉 크기 100만짜리 저장공간을 쓰기에는 부족하다.
  n번째 동전까지 써서 k의 가치를 만드는 경우의 수는 n-1번째 동전까지만 써서 k, k-v[n], k-2*v[n], …. 의 가치를 만드는 경우의 수를 모두 더한 것과 같다.
  길이 1만짜리 배열만 사용하면서, m번째 동전까지 써서 0~10000의 가치를 만드는 경우의 수를 싹 저장해 놓으면 m+1번째 동전까지 썼을 때 k의 가치를 만드는 경우의 수를 구하는 데 필요한 정보는 모두 가지고 있는 게 된다. 그러니 m+1번째 동전까지 썼을 때 0~10000의 가치를 만드는 경우의 수로 싹 갈아엎은 후 다음 단계로 계속 넘어가면 된다. 즉 길이 1만짜리 배열 두 개만 유지하면서 쭉 가면 된다.
  이렇게 n단계까지 했으면, n번째 동전까지 사용했을 때 0~10000의 가치를 만드는 경우의 수를 다 알고 있는 게 되므로 table[k]를 출력해 주면 된다.
  
  

코드(고수의 방법)

#include <iostream>
using namespace std;

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

    int table[10001]={1, };
    for(int i=0 ; i<n ; i++) {
        short v;
        cin >> v;
        for(int j=v ; j<=k ; j++) {
            table[j] += table[j-v];
        }
    }
    cout << table[k];
}

• 코멘트
  
  훨씬 간단하게 풀 수 있다.
  가장 먼저 0의 가치를 만드는 경우의 수는 1개이다.
  동전의 가치가 하나씩 입력되면(v), 그로 인해 j의 가치를 구성할 수 있는 경우의 수는 더 다양해진다. 정확히 얼마나 더 다양해지냐면, v짜리 동전이 없었을 때 j-v의 가치를 구성할 수 있는 경우의 수가 x개가 있었으면, v짜리 동전이 생겼으니 j의 가치를 구성할 수 있는 경우의 수는 x개만큼 더 생기게 된다.
  v짜리 동전의 새로운 등장으로 인해 경우의 수가 더 다양해지는 가치는 v부터 k까지가 된다. 각각 (v-v) ~ (k-v)의 기존 경우의 수 만큼 더해지게 된다.
  이렇게 하면 O(nk)의 시간 복잡도로 계산할 수 있으며 사용하는 저장공간은 길이 1만짜리 배열 한 개가 된다.