백준 2294 동전2 소스

#include <cstdio>

#define INF 11111

using namespace std;

int main()

{

int N, K; // 1<=k<=10,000

int coin[110] = { 0, }, k[10010] = { 0, }; //동전의 가치는 100,000 보다 작거나 같은 자연수

scanf(" %d %d", &N, &K);

for (int i = 0; i < N; i++){

scanf("%d", &coin[i]);

}

for (int i = 1; i <= K; i++){

int min = INF;

for (int j = 0; j < N; j++){

//현재 만들 수 있는 값보다 큰 동전일 경우

if (i - coin[j]<0) continue; //숫자를 정렬하여 입력받는 것이 아니기 때문에 break를 쓰면 안된다... 해맨 원인

//만들 수 없는 값에 대한 처리 또한 해주어야 한다.

//최저 단위 코인 미만 값은 접근하면 안된다.

else{

if (k[i - coin[j]] == -1){ continue; }

else{

min = min < k[i - coin[j]] + 1 ? min : k[i - coin[j]] + 1;

}

}

}

//만들 수 있는 경우

if (min != INF) { k[i] = min; }

//만들 수 없는 경우는 -1 저장

else{ k[i] = -1; }

}

//과정 확인용 

/*for (int i = 1; i <= K; i++){

printf("%d ", k[i]);

}

printf("\n");*/

printf("%d\n", k[K]);

return 0;

}

/*

for( k[10010])

arr[110] 가진 동전 가치 순회,  k[현재 값 - 현재 동전 가치] + 1한 값이 가장 작은 수가 최소 동전 개수이므로

min값에 저장하고 마지막에

*/