[BOJ] 9084번 : 동전 (C++)

https://www.acmicpc.net/problem/9084

9084번: 동전

 

dp문제이다. 

dp문제이므로 테이블 설정을 잘 해줘야 한다.

d[a] = b : a원을 만들 수 있는 방법의 수가 b개 라고 정의해주었다. 

 

먼저, 3원을 만들어야하고 우리에겐 1,2,3원이 있다고 가정해보자.

여기서 포인트는 "가장 마지막에 해당 동전을 사용하여 금액을 완성시키는 과정" 이다. 

1) 1원을 가장 마지막에 사용하여 금액을 완성시키기 위해서는

1원을 채우는 경우, 2원을 채우는 경우, 3원을 채우는 경우가 있다. 

1원을 가지고 1원을 채우기 위해서는 0원이 있어야 하고, 

1원을 가지고 2원을 채우기 위해서는 1원이 있어야 하고,

1원을 가지고 3원을 채우기 위해서는 2원이 있어야 한다.

 

2) 2원을 가장 마지막에 사용하여 금액을 완성시키기 위해서는

1원을 채울 순 없다. 2원부터 채울 수 있으므로

2원을 가지고 2원을 채우려면 0원이 있어야 하고,

2원을 가지고 3원을 채우려면 1원이 있어야 한다. 

 

3) 3원을 가장 마지막에 사용하여 금액을 완성시키기 위해서는

1,2원을 채울 순 없다. 3원부터 채울 수 있으므로

3원을 가지고 3원을 채우려면 0원이 있어야 한다.

 

따라서!

1원~3원을 가지고 (outer-for문)

1원이 만들 수 있는 금액은 자기 자신 금액부터 3원까지이다. (inner-for문)

 

추가로 d[0]의 값은 1이다. 

0원을 만들 수 있는 방법은 아무 동전도 사용하지 않은 경우로 1가지가 있기 때문이다.

 

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

int n,m;
int v[10005]; //동전금액
int d[10005]; //d[a]=b : a원을 만들 수 있는 방법의 수가 b개

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

    int tc; cin>>tc;
    while(tc--){
        fill(d, d+10005, 0);
        
        cin>>n;
        for(int i=1; i<=n; i++) cin>>v[i];
        cin>>m;

        d[0]=1;
        for(int i=1; i<=n; i++){
            for(int j=v[i]; j<=m; j++){
                d[j] = d[j] + d[j-v[i]];
            }
        }

        cout<<d[m]<<'\n';
    }
}

d[j] = d[j] +d[j-v[i]]; 는 j-v[i]에 v[i] 동전을 추가해주는 것이다. 

j원은 j-v[i]원에다가 v[i]을 더해주면 된다. 위에서 쓴 예시로 생각해보면, 3원은 3-1원에다가 1원을 더해주면 되는 것이다.

그래서 1원을 가지고 3원을 채우려면 이미 2원을 가지고 있어야 하고, 2원을 가질 수 있는 경우의 수가 d[2]이다. 

따라서 금액 j원에다가 v[i]를 사용하고 난 후 (= v[i]을 빼주고 난 후) 남은 금액이 j-v[i]인데 j-v[i]원을 만들 수 있는 방법의 수인 d[j-v[i]] 를 d[j]에 더해주는 것이다. 

 

 

 

문제를 이해할 때 정말 많은 도움을 받은 블로그이다!

https://yabmoons.tistory.com/556

[ 백준 9084 ] 동전 (C++)