본문 바로가기

알고리즘 풀이

백준 2294번 동전2

https://www.acmicpc.net/problem/2294


#include <cstdio>
int N, K;
int coin[101];
int money[10001];
int main(void) {
int i, j, k;
scanf("%d %d", &N, &K);
for (i = 1; i<=N; i++)
scanf("%d", &coin[i]);
for (int i = 0; i <= K; i++) {
money[i] = -1;
}
money[0] = 0;
for (int i = 1; i <= N; ++i)
{
for (int j = 0; j <= K; ++j)
{
if (j - coin[i] >= 0 && money[j - coin[i]] != -1)
{
if (money[j] == -1 || money[j] > (money[j - coin[i]] + 1) )
money[j] = money[j - coin[i]] + 1;
}
}
}
printf("%d\n", money[K]);
return 0;
}


'알고리즘 풀이' 카테고리의 다른 글

백준 6603번 로또  (0) 2018.01.15
백준 1987번 알파벳  (0) 2018.01.10
백준 2667번 단지번호붙이기  (0) 2018.01.05
백준 2609번 최대공약수 최소공배수  (0) 2018.01.01
백준 3187번 양치기 꿍  (0) 2017.12.27