[BOJ 2294] 동전 2

문제 출저 : https://www.acmicpc.net/problem/2294

 

풀이 : 

 

DP 문제입니다.

동전과 가치가 주어졌을때 가치의 합이 k가 되도록 하는 문제입니다.

데이터를 쌓을 때 주어진 value로 부터 시작해 한 칸 씩 진행하며

(계산중인 가치) 와 (계산중인 가치 - 현재가치 + 1) 중 최소값을 저장합니다.

만약 +=value로 껑충 껑충 뛰게 된다면 

3 24

1

7

10

같은 경우 3이 나와야 하는데 놓칠 수도 있습니다.

필자가 그랬음

 

#include<stdio.h>
 
int n,k,cache[10001],value;
 
int FindMin(int a, int b) { if (a < b)return a; return b; }
 
int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= k; i++)cache[i] = 10001;
    while(n--)
    {
        scanf("%d", &value);
        for (int j = value; j <=k; j++) cache[j] = FindMin(cache[j], cache[j - value] + 1);
    }
    printf("%d", cache[k]==10001?-1:cache[k]);
}