#2293번 동전 1 (C++)

문제 링크 : www.acmicpc.net/problem/2293

2293번: 동전 1

이 문제는 프로그래머스 Lv3 거스름돈과 동일하다. 

처음 풀었을때는 DP가 어려워 어거지로 이해했었는데, 다시 한 번 푸니 전보다는 보다 잘 이해됐다.

 

문제 풀이방법은 본문의 예시를 기준으로 아래 2중 for문으 도표로 풀어내면 이해할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;

int n=0,k=0,coin[101] = {0,}, sum[10001]={0,};

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k;
    sum[0] = 1;
    for(int i=1; i<=n; i++) cin >> coin[i];
    for(int i=1; i<=n; i++){
        for(int j=coin[i]; j<=k; j++){
            sum[j] += sum[j-coin[i]];
        }
    }
    cout << sum[k] << "\n";
   return 0;
}