백준 2294번 동전 2

문제 링크입니다: https://www.acmicpc.net/problem/2294

백준 2293번 동전 1(http://jaimemin.tistory.com/362)과 유사한 문제였습니다.

/*

n가지 종류의 동전이 있다.

각각의 동전이 나타내는 가치는 다르다.

이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다.

그러면서 동전의 개수가 최소가 되도록 하려고 한다.

(각각의 동전은 몇개라도 사용할 수 있다.)

*/

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 10000 + 1;

int coinNum, total; //동전 갯수, 총합

int coinValue[101], cache[MAX];

 

int minCoin(void)

{

        memset(cache, 0, sizeof(cache));

        for (int i = 1; i <= total; i++)

               cache[i] = MAX; //우선 최대치로 초기화

        //동전의 갯수를 초기화하며 최솟값 찾음

        //예를 들면 coinValue[1]=1이라면 1~total까지는 1원 동전이 j개씩 필요

        //coinValue[2]=5라면 min(1원 동전 5개, 5원 동전 1개)에서 cache[5]=1로 바뀜

        for (int i = 1; i <= coinNum; i++)

               for (int j = coinValue[i]; j <= total; j++)

                       cache[j] = min(cache[j], cache[j - coinValue[i]] + 1);

        return cache[total] == MAX ? -1 : cache[total]; //총합을 만들 수 없는 경우 -1

}

 

int main(void)

{

        cin >> coinNum >> total;

        if (coinNum < 1 || coinNum>100 || total < 1 || total >= MAX)

               exit(-1);

        for (int i = 1; i <= coinNum; i++)

               cin >> coinValue[i];

        cout << minCoin() << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~