오늘의 학습 키워드

• 그리디

[백준] 거스름돈 - 14916

• [백준] 거스름돈 - 14916
• Silver V
• 풀이시간: 20m
• C++ 풀이

문제해설

금액이 주어지면, 2원짜리 동전과 5원짜리 동전으로 거슬러 주는데, 이때 동전의 최소 개수를 출력하면 되는 문제이다.

접근법: 그리디

그리디로, 남은 동전 금액이 5로 나누어 떨어질 때까지 2를 빼주면 된다.

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

int N;
int ans = 0;
    
int main(){
    cin >> N;
    while (N > 1 && N % 5 != 0) {
        N -= 2;
        ans++;
    }
    if (N % 5 == 0) { cout << (ans + N / 5); }
    else cout << -1;
}

오늘의 회고

이번 문제는 그리디로, 비교적 간단하게 풀 수 있었다. 이 문제와 이분 탐색으로 풀어야하는 문제, 디피로 풀어야하는 문제를 구분할 수 있을까? 라는 생각이 들기도 한다. 비슷한 문제인데, 이분탐색, 디피 등 다른 유형으로 풀어야하는 문제들을 찾아서 비교해보는 것도 좋을 듯 하다.