백준 알고리즘 2294번 - 동전 2

dp로 간단히 풀 수 있는 문제.

런타임 에러가 계속 나와서 확인해봤더니 배열 최대크기를 10001으로 해서(...) 이런 멍청한 실수는 하지말자.

 

배열을 목표하는 동전 금액의 크기만큼 잡고, 주어진 동전의 값마다 dp로 memoization을 사용해서 풀어주면 된다.

 

1. 배열의 값을 전부 INF로 초기화한다.

2. 처음 주어진 동전 금액의 인덱스에 해당하는 배열의 값을 다 1로 놓는다.

3. 배열을 돌면서, INF가 아닌 배열 값을 발견하면 거기에 동전 값을 더해준 인덱스에 1을 더해서 저장하거나, 해당 인덱스에 있는 배열 값이 더 작다면 그대로 유지한다.

4. 인덱스가 금액 이므로 dp[k]가 INF가 아니라면(방문한적 있다면) 그 값을 출력, 

INF라면 방문한 적 없는 것이므로 -1을 출력한다 

소스코드

// Example program
#include <algorithm>
#include <iostream>
#define INF 987654321
 
using namespace std;
 
int main()
{
    int dp[100001];
    int arr[101];
 
    int n,k;
    cin>>n>>k;
    //방문여부를 INF냐 아니냐로 구분하기위해 dp의 모든 인자를 INF로 놓는다
    for(int i=1;i<=k;i++) dp[i]=INF;
        
    //한번만에 갈 수 있는 동전 인덱스는 다 1로 지정한다.
    for(int i=1;i<=n;i++) 
    {
        cin>>arr[i];
        dp[arr[i]]=1;
    }
    for(int i=1;i<=k;i++){
        //전에 계산이 된 동전 액수 인덱스만 계산한다.
        if(dp[i]!=INF){
            for(int j=1;j<=n;j++){
                int now=i+arr[j];
                //동전 크기만큼 인덱스를 이동시켜나간다.
                if(now<=k) dp[now]=min(dp[i]+1,dp[now]);
            }
        }
    }
    //INF를 방문 여부로 지정했으니 해당 인덱스가 INF라면 가는 방법이 없는 것.
    if(dp[k]!=INF) cout<<dp[k];
    else cout<<-1;
}