[99클럽/코딩테스트 챌린지/C++] 동전 거스름돈 문제에서 그리디 접근법 활

문제 링크 : 

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

문제 설명

춘향이는 2원과 5원짜리 동전만으로 손님에게 최소 개수의 동전으로 거스름돈 NNN원을 주어야 한다. 2원과 5원짜리 동전이 무한정 있을 때, 정확히 NNN원을 거슬러 줄 수 있는 최소 동전 개수를 구하는 문제이다.

접근법

처음에는 이 문제에 그리디 알고리즘이 필요하다는 점을 인지하지 못했지만, 문제를 분석하면서 각 단계에서 최적의 선택을 해야 함을 깨달았다.
그리디 알고리즘을 적용하기 위한 조건은 다음과 같다:

 

1, 큰 단위의 동전 우선 사용: 5원짜리 동전이 2원짜리보다 크기 때문에, 큰 단위인 5원짜리를 우선적으로 사용해 거슬러 줌으로써 동전 개수를 최소화할 수 있다.

 

2, 남은 금액에 맞는 조정: 5원으로 나누어떨어지지 않는 경우에는 2원을 사용해 필요한 동전 수를 최소화한다.

코드 설명

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N = 0;

    std::cin >> N;

    int count = 0;
    while (N > 0)
    {
        if (N == 1)
        {
            std::cout << -1 << '\n';
            return 0;
        }
        if (N % 5 == 0)
        {
            N -= 5;
        }
        else if (N % 2 == 0)
        {
            N -= 2;
        }
        else if (N >= 5)
        {
            N -= 5;
        }
        else if (N >= 2)
        {
            N -= 2;
        }
        count++;
    }

    std::cout << count << '\n';
    return 0;
}

배운 점

이번 문제를 통해 그리디 알고리즘을 적용할 수 있는 조건을 명확히 이해하게 되었다. 특히, 큰 단위 선택이 전체 최소 결과를 보장할 수 있는 문제일 때 그리디 알고리즘이 적합하다는 점을 깨달았다.

이 경험을 통해 동전 거스름돈 문제와 같은 경우, 큰 단위 동전부터 사용하는 전략이 최적의 선택임을 알게 되었고, 앞으로 유사한 문제를 만날 때 그리디 접근 방식을 쉽게 판단할 수 있을 것이다.

결론

이번 문제는 그리디 알고리즘을 통해 최소한의 동전 수로 거스름돈을 제공하는 최적 해법을 찾는 문제였다. 큰 단위의 동전을 우선적으로 사용하여 효율적으로 문제를 해결할 수 있었고, 그리디 접근법의 유용성을 다시 한번 체감했다. 이 경험을 바탕으로 앞으로도 최적 선택이 결과에 직접적으로 반영되는 문제에서 그리디 알고리즘을 신속하게 적용할 수 있을 것이라 생각한다.