[C/C++] 백준 #2294 동전 2(동적 계획법)

#2294 동전 문제도 #2293 동전 문제와 비섯합니다.  단, 가치가 같은 동전이 주어질 수 있다는 것 뿐으로 크게 고려 대상은 아닙니다.

 

coins

 

문제의 링크입니다.

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

2294번: 동전 2

 

참고할 수 있는 이전 문제 링크입니다.

https://sdev.tistory.com/1333

[C/C++] 백준 #2293 동전 1(동적 계획법)

 

이번 문제는 경우의 수 문제가 아니고, 가장 적은 개수의 동전으로 만드는 것입니다.

\(v_{n, k}\)라는 배열을 정의했습니다.  \(v_{n,k}\)는 n개의 주어진 동전을 가지고 k라는 값을 만들 수 있는 최소 동전의 개수입니다.

\[ v_{*, 0} = 0 \]

\[ v_{i, s} = min ( v_{n, s-c_i} + 1, v_{n-1, s} ) \]

형태로 설정을 했습니다.

 

이전의 \(v_{n, k}\)을 받아야 하지만, 저는 오름차순 형태로 처리를 함으로써, 해당 문제를 해결했습니다.  점근적 시간 복잡도는 \(O(NK)\) 입니다.

 

제가 작성한 소스입니다.

//--------------------------------------------
//    baekjoon #2294
//        - by Aubrey Choi
//        - created at 2019-09-11
//        - modified at 2021-07-16
//--------------------------------------------
#include <stdio.h>

int MIN(int a, int b) { return a<b?a:b; }
int main()
{
    int n, k, s, v[10001];
    scanf("%d%d",&n,&k);
    for(int i=0;i<=k;i++) v[i]=100000;
    v[0]=0;
    while(n--)
    {
        scanf("%d",&s);
        if(s>k) continue;
        for(int i=s;i<=k;i++) v[i]=MIN(v[i-s]+1, v[i]);
    }
    printf("%d\n", v[k]==100000?-1:v[k]);
}