[코드업] 거스름돈 II (C++)

거스름돈 II

 

문제

이 문제는 자동판매기에서 거스름돈을 돌려줄 때,

최소한의 동전을 사용하여 거스름돈을 돌려주는 방법을 구하는 문제이다.

풀이

그리디로 접근하기 쉬운 문제지만, 그리디로 문제를 풀면 정답이 아닌 경우가 발생한다.

예를 들어, 동전 종류가 1원, 3원, 4원이 있고 거슬러 주어야 할 돈이 6원이라면,

그리디 알고리즘은 4원 1개, 1원 2개로 거슬러준다. 하지만 최적의 해는 3원 2개이기 때문에 틀린다.

 

그래서 이 문제는 DP (다이나믹 프로그래밍)을 사용해서 풀어야한다.

 

DP를 이용하여 거슬러 줘야할 금액까지의 최소 갯수를 저장하면서 목표 금액의 최소 거스름돈 갯수를 구하면 된다.

 

6원의 거스름돈을 구할 때는 1, 3, 4원 전부 다 거스름돈을 걸러줄 수 있다.

1원을 거슬러 줄 때는 5원의 최소 거스름돈 갯수(2) + 1개 (1원),

3원을 거슬러 줄 때는 3원의 최소 거스름돈 갯수(1) + 1개 (3원),

4원을 거슬러 줄 때는 2원의 최소 거스름돈 갯수(2) + 1개 (4원)

 

이 중 가장 적은 3원을 거슬러 줄 때 최솟값인 2개가 6원의 최소 거스름돈 갯수이다. (6 == 3 + 3)

#include <iostream>
#include <vector>
// https://codeup.kr/problem.php?id=2634&rid=0
using namespace std;

int main() {
    int change, n;
    cin >> change >> n; // 거스름돈 액수, 종류의 갯수 입력

    vector<int> changeTypes(n); // 거스름돈 종류
    for (int i = 0; i < n; ++i) { // 거스름돈 종류 입력 
        cin >> changeTypes[i];
    }

    // 거스름돈의 갯수를 저장하는 벡터
    vector<int> dp(change + 1, 10001); // 동전의 최댓값이 10000원이기 때문에 10001개로 초기화
    dp[0] = 0; // 거스름돈이 딱 맞아 떨어졌을 때 == 0

    for (int i = 1; i <= change; ++i) { // 금액 별 거스름돈 갯수 저장
        for (int j = 0; j < n; ++j) {
            if (i - changeTypes[j] >= 0) { // 거슬러 줄 수 있을 때
                dp[i] = min(dp[i], dp[i - changeTypes[j]] + 1);  // 금액 별 최소 갯수 저장
            }
        }
    }

    cout << dp[change] << endl; // 입력 금액의 거스름돈 갯수 출력

    return 0;
}

 

코드를 이해하는 데 어려움이 있는 부분이 있거나 개선할 부분이 있다면 댓글을 달아주세요.

 

CodingTestPractice/CodeUp/관계기반 설계/거스름돈 II.cpp at main · seungdo1234/CodingTestPractice