[백준 2293번 C/C++] 동전 1

 

[백준 2293번 C/C++] 동전 1

 

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

2293번: 동전 1

 

---

 

해결방안

 

Dynamic Programming (DP) 동적계획법

 

---

 

시도 코드 - 시간초과

 

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

int n, k;
vector<int> v;
vector<vector<int>> dp;
int coin[101];

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

    cin >> n >> k;
    v.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }

    dp.resize(n + 1, vector<int>(k + 1, 0));

    dp[0][0] = 1; // 0원을 만드는 방법은 아무 동전도 사용하지 않는 경우 1가지 방법이 있음

    for (int j = 1; j <= n; j++)
    {
        for (int i = 0; i <= k; i++)
        {
            dp[j][i] = dp[j - 1][i]; // 이전 동전까지 사용한 경우의 수를 복사

            if (i >= v[j])
                dp[j][i] += dp[j][i - v[j]]; // j번째 동전을 사용하여 i원을 만들 수 있는 경우의 수를 더함
        }
    }

    cout << dp[n][k];

    return 0;
}

 

---

 

코드

 

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

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

    int n, k;
    cin >> n >> k;

    vector<int> coins(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> coins[i];
    }

    vector<int> dp(k + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = coins[i]; j <= k; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }

    cout << dp[k];

    return 0;
}

 

 

 

벡터에 동전 조작값 입력

vector<int> coins(n + 1);
for (int i = 1; i <= n; i++) {
    cin >> coins[i];
}

동전의 조작값들을 저장할 coins 벡터를 선언합니다. 벡터의 크기는 n+1로 지정되며, 이는 동전값을 1부터 시작하는 것을 고려한 것입니다.

 

동전값 입력은 반복문을 사용합니다. n개의 동전 종류로 이루어진 인덱스를 가지는 coins에 각 동전 값들을 순차적으로 입력받습니다.

 

배열 초기화

vector<int> dp(k + 1, 0);
dp[0] = 1;

궁극적으로 동전의 종류와 조작값을 이용해 만들어 낼 수 있는 경우의 수를 기록할 dp 배열을 선언합니다. 다만 이 때 배열은 vector로 선언합니다.

 

배열 dp의 크기는 k + 1로 하였습니다. dp 배열을 0으로 초기화하고, dp[0] = 1로 초기화하여, 동전을 하나도 사용하지 않았을 때 0을 만들 수 있다는 것을 기준으로 잡아줍니다.

 

중첩 루프를 이용한 DP

for (int i = 1; i <= n; i++) {
    for (int j = coins[i]; j <= k; j++) {
        dp[j] += dp[j - coins[i]];
    }
}

위 코드는 동전 조작값을 이용해 만들 수 있는 모든 경우의 수를 구하는 DP(Dynamic Programming) 알고리즘을 실행하는 부분입니다.

 

바깥쪽 반복문은 동전 종류 수 만큼 진행합니다. 즉, 2개의 동전 조작값을 입력했다면 바깥쪽 반복문은 i=1 ~ i=2까지 실행됩니다.

 

안쪽 반복문은 coins[i]부터 k까지 차례대로 값을 증가시킵니다. 즉, 2개의 동전 조작값을 입력한 경우, j는 3~10까지 반복됩니다. 이 때 dp[j - coins[i]]가 이전에 계산된 경우의 수를 의미합니다. 알고리즘은 이전 경우의 수(dp[j - coins[i]])에서 현재 동전의 조작값을 더하여 합이 j가 되는 경우를 계산합니다.

 

이전 경우의 수를 합하여 현재 가능한 새로운 경우의 수를 기록한 후, 최종적으로 k를 만들어낼 수 있는 총 가능한 경우의 수를 출력합니다.

 

출력

cout << dp[k];

이제 k를 만들어낼 수 있는 가능한 경우의 수를 출력합니다.

 

---