[코드트리 챌린지] 4주차 DP l - 아이템을 적절히 고르는 문제 / 동전 거슬러주기

 

https://www.codetree.ai/missions/2/problems/coin-change/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

코드:

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[105]; // 동전 종류 저장
int dp[10005]; // 금액 m <= 10000 이므로 크기를 10000 이상으로 설정

void Initialize() {
    // 0원은 동전을 사용하지 않으므로 0
    dp[0] = 0;

    // 최소 동전의 수를 구하여야 하므로 
    // dp 값을 큰 값으로 설정해줌
    // 만약 거슬러줄 수 없는 경우는 값이 1000000 인채로 있게됨.
    // 이때 INT_MAX는 사용 불가 (overflow로 인한 값 오류가 발생가능)
    for (int i = 1; i <= m; i++) {
        dp[i] = 10000000;
    }
}

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

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    Initialize();

    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < n; j++) {
            // 현 금액이 가지고 있는 동전의 값보다 클 경우
            if (i >= arr[j]) {
                // dp[현 금액 - 동전 값] + 1 로 초기화 시켜준다.
                dp[i] = min(dp[i], dp[i - arr[j]] + 1);
            }
        }
    }

    // 그 금액을 만들 수 없는 경우도 존재하므로 if문으로 구별
    if (dp[m] == 10000000)
        cout << -1;
    else
        cout << dp[m];
    
}

n과 m을 입력받고 동전의 값을 저장할 arr 배열을 초기화합니다.

Initialize() 함수를 통하여 dp 값을 초기화해주도록 합니다.
이때 우리가 구해야하는 값을 최소 동전 수 이므로 dp의 값은 최대한 큰 수로 설정해주도록 합니다.
그러나 INT_MAX로 설정해서는 안되는데 이후 dp의 값을 채울 때 + 1을 해주면서 overflow가 발생해
매우 작은 값이 저장될 수 있기 때문입니다.

이후 for문을 통해 현재 금액이 가지고 있는 동전의 값보다 큰 경우에만 dp값을 삽입하도록 합니다.
이때 dp의 점화식은 dp[i] = max(dp[i - arr[j]) + 1) (0 <= j < n , i >= arr[j]) 입니다.
dp[현 금액 - 동전 값]이 존재할 경우 dp 값이 삽입됩니다.

dp[i] : i 금액을 채우기 위해 필요한 최소한의 동전 수