[C++,DP] 백준 2294번 동전2 문제풀이

문제링크

백준 2294번 동전2

2294번: 동전 2

DP문제를 하나 더 풀어보았다. 어려운 듯하면서 쉬운 듯 했다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
 
int main(){
    int N,K;
    cin>>N>>K; 
    vector <int> coin(N,9999);
    int DP[10001];
    memset(DP, -1, 10001 );
    
    for(int i=0;i<coin.size();i++){
        int n;
        cin>>n;
        coin[i]=n;
    }
    DP[0]=0;
 
    sort(coin.begin(),coin.end(),greater <int>());
    
    for(int i=0;i<K+1;i++){
        for(int j=0;j<coin.size();j++){
            
            if((i+1)%coin[j]==0){
                int tmp=DP[i+1-coin[j]]+1;
                if(DP[i+1]>tmp||DP[i+1]==-1)DP[i+1]=tmp;
            }
        
        }
    }
    //for(int i=1;i<K+1;i++)cout<<DP[i]<<" ";
    cout<<DP[K];
    return 0;
}

 

문제를 보고 처음 바로 짠 코드이다. DP를 사용하여 어느정도 맞게 접근하였다. 

하지만 무슨 이윤지는 모르겠으나 만들려는 수가 받은 동전으로 나누어 떨어져야 DP를 실행해야한다는 생각으로 위의 코드를 짜고 틀려버렸다...ㅋㅋ

예제의 동전이 1,5,12라서 1로 무조건 나누어지기 때문에 의심없이 코드를 짰다.

하지만 틀린후에 테스트케이스를 몇 개 더 스스로 만들어 진행하니 오점이 보였다..ㅜㅜ 

앞으로는 예제의 코드말고도 테스트케이스를 하나 더 만들어 코드를 생각해야겠다. 

 

딱히 아이디어가 떠오르지 않아 다른 여러 코드를 참고하여 다시 짜기로 했다.

 

#include<cstdio>
#include<iostream>
 
using namespace std;
 
int coins[101];
int dp[10001];
 
int main(){
    int n,k;
    scanf("%d %d",&n,&k);
    fill_n(dp,k+1,1987654321);
    for(int i=1;i<=n;i++){
    scanf("%d",&coins[i]);
    if(coins[i]>k)continue;
    dp[coins[i]]=1;
    }
    for(int i=0;i<n;i++){
        for(int j=coins[i+1];j<=k;j++){
            
            if(dp[j]>dp[j-coins[i+1]]+1)dp[j]=dp[j-coins[i+1]]+1;
        }
    }
 
    printf("%d ",dp[k]==1987654321?-1:dp[k]);
    
}

 

 

다시 짜고 AC를 받은 코드이다. 

여러 사람 코드를 보니 우선, C++인데도 cstdio를 include하는 사람이 여럿있었다.

stdio.h와 cstdio의 차이점이 궁금해져 조사해보니 C++에서도 C를 사용할 수 있는데 그럴러면 cstdio를 include하면 된다는 것이다. 

대부분이 사람들이 cstdio를 선호하는 이유는 입출력에서 cin, cout 보다 scanf, printf가 속도가 빠르기 때문이다. 이번 기회에 나도 cstdio를 사용하기로 했다.

 

또한 위에서 짠 코드와 같이 나는 배열 대신 vector를 선호하는데 보통 전역변수로 간단하게 배열 형태로 만들고 시작하는 사람이 많았다.

이유를 조사해보니 메모리측면에서 간단하게 선언을 하고 시작하는게 좋고 또 지역 변수보다 전역변수로 사용하는게 성능이 좋다는 것이다.  

 

이외에도 배열을 초기화하는 법에 대해 생각하고 방법 몇 가지를 배울 수 있었다. 

간단하게 for문으로 초기화하는 법

iostream에 포함된 fill_n 사용법 (배열이름,초기화 길이, 초기화 수 )

string.h에 포함된 memset 사용법이 있었는데 (배열이름,초기화수,배열 전체의 크기)

셋다 쓸일이 있어서 익히기로 했다.

 

 

코드를 작성하고 알고리즘은 맞는 거 같은데 자꾸 위와 같이 실행오류가 떠서 한 30분 고민해보니 입력값과 배열의 크기 때문에 없는 인덱스 값을 집어넣는 경우가 발생해서 그런 것이였다. 15번째 줄이 오류 방지 줄이다. 문제와 데이터 입력값을 신중이 고려해야 함을 느꼈다.