9084 2293 2294 동전

난 동전 1이 있는지 모르고 동전, 동전 2, 동전 1 순으로 풀었는데 다 비슷한 문제였다.

 

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

9084번: 동전

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int k; cin>>k;
    while(k--){
        int d[10003]={0,},coin[23];
        int n; cin>>n;
        for(int i=1;i<=n;i++) cin>>coin[i];
        int m; cin>>m;
        d[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=coin[i];j<=m;j++){
                d[j]+=d[j-coin[i]];
            }
        }
        cout<<d[m]<<'\n';
    }
    return 0;
}

d[n]은 숫자 n을 만들 수 있는 경우의 수이다.

1~i번째 동전으로 숫자 1~m을 만들 수 있는 경우의 수를 갱신해가는 알고리즘이다.

 

1원 동전으로 숫자 1~m을 만든다고 하면 d[1~m]=1 이 된다. 

그 다음 2원 동전으로 숫자 2~m을 만든다고 하면 앞서 1원 동전으로 숫자를 만들었던 경우의 수에 더한다. 

예를 들어 2원 동전으로 3원을 만든다고 치면 d[3]에 d[1]을 더한다.

현재 2원만 사용할 수 있으므로 1원을 만드는 경우의 수에 2원을 붙이면 3원이 되기 때문이다.

 

이렇게 O(N^2) 코드를 완성할 수 있다.

---

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

2293번: 동전 1

위와 같은 방법으로 코드를 짜면 된다.

#include <bits/stdc++.h>
using namespace std;
int coin[103],d[10003];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k; cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>coin[i];
    d[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=coin[i];j<=k;j++)
            d[j]+=d[j-coin[i]];
    cout<<d[k];
    return 0; 
}

---

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

2294번: 동전 2

#include <bits/stdc++.h>
using namespace std;
int coin[103],d[10003];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,k; cin>>n>>k;
    fill(d,d+k+1,0x7f7f7f7f);
    for(int i=1;i<=n;i++) cin>>coin[i];
    d[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=coin[i];j<=k;j++){
            d[j]=min(d[j],d[j-coin[i]]+1);
        }
    }
    if(d[k]!=0x7f7f7f7f) cout<<d[k];
    else cout<<-1;
    return 0; 
}

min을 사용하므로 배열을 0x7f7f7f7f로 초기화한다.

이전과 마찬가지로 coin 종류별로 loop를 돌면서 숫자 n을 만드는데 사용되는 코인 수를 갱신하게 했다.

d[n]은 n을 만드는데 쓰인 코인의 최솟값이다. 

coin 값이 3일 때를 보면 d[n]= 기존의 d[n] or d[n-3]+1 이라고 할 수 있다.

둘 중 더 작은 값을 택한다.