Gidhub BE Developer

[BOJ] - 동전 2

2018-03-21
goodGid

Problem

Problem URL : 동전 2

Screenshots of Problem Explain

[1] Answer Code (18. 03. 21)


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

int c[101]; // c is coin
int dp[10001];

int main(){
    for(int i=1; i<=10001; i++)
        dp[i] = 987654321;
    
    int n,k;
    cin >> n >> k;
    
    for(int i=1; i<=n; i++)
        scanf("%d", c+i);
    
    for(int i=1; i<=n; i++){
        for(int j=c[i]; j<=k; j++){
            dp[j] = min( dp[j], dp[j - c[i]] + 1 );
        }
    }
    
    cout << ( dp[k] != 987654321 ? dp[k] : -1 ) << endl;
    return 0;
}

Review

  • 2년전에 풀었던 문제였다.

  • 오랜만에 동전 문제를 접하니 어려웠다.


[2] Answer Code (18. 09. 14)

#include<iostream>
#define min(a,b) a > b ? b : a
using namespace std;

int c[101];
int dp[10001];

int main(){
    int n,k;
    cin >> n >> k;
    
    for(int i=0; i<n; i++)
        scanf("%d",c+i);
    
    for(int i=1; i<=k; i++)
        dp[i] = 2e9;
    
    for(int i=0; i<n; i++){
        for(int j=c[i]; j<=k; j++){
            dp[j] = min( dp[j] , 1 + dp[j-c[i]] ) ;
        }
    }
    if( dp[k] == 2e9)
        dp[k] = -1;
    cout << dp[k] << endl;
    return 0;
}

Review

  • 큰 문제 없이 풀었다.

Comments

Content