🪙 BOJ 14916번: 거스름돈 – 최소 동전 개수 구하기 C++

🪙 BOJ 14916번: 거스름돈 – 최소 동전 개수 구하기

🔍 문제 설명

춘향이는 편의점에서 일하고 있어요. 손님이 물건을 사고 난 뒤, 거스름돈을 2원짜리와 5원짜리 동전으로만 달라고 했습니다.
춘향이는 동전을 최소 개수로 거슬러주고 싶어요.

📥 입력

• 정수 n (1 ≤ n ≤ 100,000): 거슬러줘야 할 금액

📤 출력

• 2원짜리와 5원짜리를 이용해서 n원을 만들 수 있다면, 필요한 동전 개수의 최솟값을 출력하세요.
• 만들 수 없다면 -1을 출력하세요.

🧪 예제

입력	출력	설명
13	5	5×1 + 2×4 = 5개
14	4	5×2 + 2×2 = 4개
3	-1	5나 2로 만들 수 없음

---

💡 풀이 아이디어

✅ 접근 방법 (단순 구현)

1. 5원짜리 동전을 최대한 많이 쓰는 것이 유리합니다.
2. 먼저 n원을 5로 나누어 가능한 한 5원짜리 동전을 최대한 사용해 봅니다.
3. 나머지를 2원짜리로 채워서 n원이 되는지 확인합니다.
4. 만약 안 된다면 5원짜리 개수를 하나 줄이고 다시 확인해봅니다.
5. 2원짜리만으로도 만들 수 없는 경우에는 -1을 출력합니다.

---

📄 전체 코드 (원래 작성한 코드)

#include <iostream>
using namespace std;

int main(void)
{
    int N, cnt = 0;
    cin >> N;

    int five = N, five_cnt = 0, two = 1;

    while (five >= 5) {
        five -= 5;
        five_cnt++;
    }

    if (five == 0) {
        cout << five_cnt << endl;
        return 0;
    }

    while (1) {
        if (5 * five_cnt + 2 * two == N) {
            cout << five_cnt + two << endl;
            break;
        }
        else if (5 * five_cnt + 2 * two > N) {
            five_cnt--;
        }
        else {
            two++;
        }

        if (two * 2 > N) {
            cout << -1 << endl;
            break;
        }
    }

    return 0;
}

---

🧩 코드 분석 (라인별 설명)

🔹 초기 설정

int N, cnt = 0;
cin >> N;
int five = N, five_cnt = 0, two = 1;

🔹 5원짜리 최대한 사용

while (five >= 5) {
    five -= 5;
    five_cnt++;
}

🔹 5원짜리만으로 해결 가능한 경우

if (five == 0) {
    cout << five_cnt << endl;
    return 0;
}

🔹 두 동전 조합 시도

while (1) {
    if (5 * five_cnt + 2 * two == N) {
        cout << five_cnt + two << endl;
        break;
    }
    else if (5 * five_cnt + 2 * two > N) {
        five_cnt--;
    }
    else {
        two++;
    }

    if (two * 2 > N) {
        cout << -1 << endl;
        break;
    }
}

---

🔧 개선된 코드 (간단한 탐욕법 적용)

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    int cnt = 0;
    while (N >= 0) {
        if (N % 5 == 0) {
            cnt += N / 5;
            cout << cnt << endl;
            return 0;
        }
        N -= 2;
        cnt++;
    }
    cout << -1 << endl;
    return 0;
}

---

💡 개선 코드 아이디어

• 매번 전체 금액 N이 5로 나눠지는지 확인합니다.
• 안 나눠지면 2원짜리 하나를 더 써서 N을 줄입니다.
• 반복하면서 5의 배수가 되면 바로 해결!

---

✅ 개선 코드 설명

단계	동작
1	5로 나눠지면 끝!
2	아니라면 2를 빼고, 동전 개수 1 증가
3	다시 5로 나눠지나 확인
4	그래도 안 되면 또 2를 빼고 반복...
5	N이 0보다 작아지면 답 없음 → -1

---

📌 마무리 요약

내용	설명
핵심 알고리즘	그리디 알고리즘 (큰 동전 먼저 쓰기)
왜 5원 먼저?	동전 개수를 줄이려면 큰 단위 먼저 쓰는 게 이득
실패 조건	5와 2로 어떤 조합도 안 되는 경우
좋은 구현 방식	반복문 하나로 간단히 처리 가능