[BOJ-2294]동전2

런타임에러를 2번받았는데 경계값 조건을 잘못 설정 했나보다. 

일단 동전을 바꾸기 위해서 

바꿔야 하는 돈 k

돈의 갯수 n

그렇다면 값을 가져올 곳이 a라면 0...a..k 순서로 값이 나열이 되어있다. 

그럼다면 a+1 .... k 까지 저장된 값에서 값을 끌어온다. 만약 값을 가져올 수 없다면 INF 무한대(미리설정한 값)이 넣는다.

 

로 값을 가져와서 갱신한다. 

#include<cstdio>
#include<cstring>
// 계단이랑 비슷한거 같은데
int coin[100];
int dp[222222];
int n, k;
const int INF = 0x00FFFFFF;
int min2(int a, int b){
    return (a>b)?b:a;
}
 
int dy(int t){
    if(t >= k) return INF;
    int &ret = dp[t];
    if(ret != -1) return ret;
    ret = INF;
    for(int i = 0 ; i < n ; i++){
        if(dp[t+coin[i]] == -1 || t+coin[i] > 11111) continue;
        ret = min2(ret, dp[t+coin[i]]);
    }
    if(ret != INF) ret++;
    
    return ret;
}
 
int main(){
    scanf("%d %d", &n, &k);
    memset(dp, -1, sizeof(dp));
    dp[k] = 0;
    for(int i = 0 ; i < n ; i++){
        scanf("%d", &coin[i]);
        if(k-coin[i] >= 0) dp[k - coin[i]] = 1;
    }
    
    for(int i = k ; i >= 0 ; i--){
        dy(i);
    }
 
    if(dp[0] == INF) printf("-1");
    else printf("%d", dp[0]);
    return 0;
}