백준 2293번 동전 1

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

다이나믹 프로그래밍이면 무조건 재귀로 풀려고 했던 모습을 반성하게 되는 문제였습니다.

조금만 생각해보면 알고리즘은 상당히 쉬웠던 문제였습니다.

/*

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

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

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

그 경우의 수를 구하시오

*/

#include <iostream>

#include <cstring> //memset

using namespace std;

 

int K; //총합

int N; //동전의 개수

int coinValue[101], cache[10001];

 

int coin(int K)

{

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

        cache[0] = 1; //0원은 모든 동전을 세지 않았을 경우(1가지)

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

               for (int j = coinValue[i]; j <= K; j++)  //K 뿐만 아니라 K 이하 합에 대해 경우의 수를 모두 구한다

                       cache[j] += cache[j - coinValue[i]];

        return cache[K];

}

 

int main(void)

{

        cin >> N >> K;

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

               cin >> coinValue[i];

        cout << coin(K) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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