[BOJ/C++] 동전 1(2293번)

1. 개요

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

2293번: 동전 1

1-1. 설명

n가지 종류 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해 그 가치의 합이 k원이 되도록 한다. 그 경우의 수를 구하는 프로그램을 작성한다. 각각의 동전은 몇 개라도 사용 가능하다. 

1-2. 제한 사항

 - 첫 줄에 n과 k가 주어지며 n은 1 이상 100 이하, k는 1 이상 10,000 이하

 - 다음 n개 줄에는 각각의 동전 가치가 주어지며, 동전의 가치는 100,000 이하 자연수

---

2. 구현

2-1. 풀이

문제를 확인한 후 DP를 이용해 푸는 문제임은 이해하였으나, 점화식을 어떤 식으로 도출해야 할지 감이 안와 다른 사람의 풀이를 참고하였다. 우선 동전을 저장해준 후, dp 배열을 이용해 저장한다. dp는 K+1개만큼 선언해주었다. 메모리 또한 4MB로 제한적이므로, 메모리풀 형식은 사용하지 않고 지정된 크기만큼 배열들을 지정해주었다. 후에 저장된 동전만큼 반복문을 이용하여 1에서 K까지 경우의 수를 채운다. 예를 들면 동전이 1원, 2원, 3원 존재할 때 1원을 이용해 dp를 채웠을 때, 그리고 1원과 2원을 동시에 이용해 dp를 채웠을 때, 마지막으로 3가지 동전을 모두 사용하였을 때이다. 

문제에 있는 예시를 이용해 차근차근 구해보자. 우선 첫번째 코인인 1원만을 이용해 dp를 구한다. 1원만을 이용하면, 1일때는 1, 2일 때는 1+1, 3일 때는 1+1+1, k일 때는 1+1+...+1(k개) 이런식으로 경우의 수는 1개씩 나올 것이다. 그럼 이를 이용해 표를 채워준다. 

1원을 이용한 경우의 수

이후에는 1원과 2원을 이용한 경우의 수를 구한다. 앞서 저장된 dp의 값에서 누적하여 더하면 된다. 예를 들면, 1원일 때는 2원이 들어갈 수 없으므로 그대로 1, 2원일때는 1+1, 2 해서 2가지, 3원일 때는 1+1+1, 1+2해서 2가지 ... k만큼 구하면 된다. 

1원, 2원을 이용한 경우의 수

앞서 정리한 내용을 토대로 점화식이 dp[j] = dp[j] + dp[j - coin[i]]임을 도출해낼 수 있다. j는 coin[i]부터 K까지의 수를 for문으로 돌린 것이며, i는 현재 코인 값이다. 마지막으로 i=3인 5원까지 사용했을 때 경우의 수를 누적하여 합산한다. 앞서 저장된 dp[1]~dp[4]까지는 5원을 사용하지 못하므로, 숫자는 고정된다. dp[5]부터는 앞서 저장한 누적합에서 경우의 수를 구해 더하면 끝이다. 이 또한 점화식을 이용해 구하면 동일한 것을 확인할 수 있다. 

1원, 2원, 5원을 이용한 경우의 수

여기서 최대 경우의 수는 dp[10]인 10임을 확인할 수 있다. 경우의 수를 구하는 것은 어렵지 않았으나, 점화식을 도출하는 과정에서 어떻게 해야할 지 감이 잡히지 않아 풀이를 참고하였다. 조금 더 연습을 해야할 것 같다. 

2-2. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, K;
    cin >> N >> K;
    vector<int> coins(N), dp(K+1);
    for (int i = 0; i < N; i++) cin >> coins[i];

    dp[0] = 1;
    for (int coin : coins) { // 저장된 코인 반복
        for (int j = coin; j <= K; j++) { // 현재 코인부터 K까지
            dp[j] += dp[j - coin];
        }
    }
    cout << dp[K];
    return 0;
}