🧾 문제 설명 (BOJ 14916번: 거스름돈) 파이썬

🔷 🧾 문제 설명 (BOJ 14916번: 거스름돈)

문제 링크: https://www.acmicpc.net/problem/14916

춘향이는 편의점에서 근무 중이며, 손님이 2원짜리와 5원짜리 동전만 사용해서 거스름돈을 달라고 요청했습니다.
단, 동전의 개수가 최소가 되도록 거슬러 줘야 합니다.
주어진 거스름돈 n에 대해, 가능한 최소 개수의 동전 개수를 출력하는 프로그램을 작성하세요.
만약 정확히 거슬러 줄 수 없다면 -1을 출력해야 합니다.

• 입력: 정수 n (1 ≤ n ≤ 100,000)
• 출력: 최소 동전 개수 또는 -1

🧪 예제

입력	출력	설명
13	5	5 + 2×4 = 5개
14	4	5×2 + 2×2 = 4개
15	3	5×3 = 3개

---

🔷 🧮 🥇 첫 번째 파이썬 코드

N = int(input())
five = N
five_cnt = 0
two = 1

# 먼저 최대한 5로 나누기
while five >= 5:
    five -= 5
    five_cnt += 1

# 만약 5로만 딱 나눠졌다면 바로 출력
if five == 0:
    print(five_cnt)
else:
    while True:
        if 5 * five_cnt + 2 * two == N:
            print(five_cnt + two)
            break
        elif 5 * five_cnt + 2 * two > N:
            five_cnt -= 1
        else:
            two += 1

        if two * 2 > N:
            print(-1)
            break

🔷 🧠 첫 번째 코드의 내 논리 설명

단계	사고의 유형	설명
1	그리디 시작	N에서 5를 가능한 만큼 빼면서 five_cnt를 누적
2	조합 판단	5*five_cnt + 2*two 조합이 정확히 N이 되는 순간을 찾음
3	값 조절	초과 시 → five_cnt 줄임 / 부족 시 → two 늘림
4	실패 조건 방지	two*2 > N이 되면 → 종료하고 -1 출력

5원짜리를 최대한 써보되, 안 맞으면 2원짜리를 조합해가며 N을 맞추는 탐색형 사고.
그리디 + 완전탐색 브루트포스가 결합된 구조입니다.

---

🔷 🥈 두 번째 파이썬 코드 (개선된 버전)

k = int(input())
coin = 0
dc = False

while k >= 0:
    if k % 5 == 0:
        coin += k // 5
        print(coin)
        dc = True
        break
    else:
        k -= 2
        coin += 1

if not dc:
    print(-1)

🔷 🧠 두 번째 코드의 내 논리 설명

단계	사고의 유형	설명
1	반복적 감소	k를 2씩 줄이면서 k % 5 == 0이 되는 순간을 기다림
2	정확히 나눠지는 순간	5로 나눠지면 해당 몫을 더해서 총 동전 개수 계산
3	불가능한 경우	k < 0까지 반복해도 조건 못 맞추면 -1 출력

"안 되면 2를 빼면서, 5로 나눠질 수 있는 순간을 기다리자"라는 직관적이면서 효율적인 방식입니다.
그리디 사고에 가깝고, 구현이 단순합니다.
→ while k >= 0: 이 구조 덕분에 조건 처리도 깔끔합니다.

---

🔷 ✅ 비교 및 결론

항목	첫 번째 코드	두 번째 코드
방식	5부터 채우고 2를 조합	2부터 줄이면서 5에 맞추기
전략	그리디 + 브루트포스	단순 그리디적 반복
코드 길이	상대적으로 복잡	간단하고 명확
종료 조건	따로 if로 제어	while k >= 0로 자연스럽게 처리
효율성	충분히 좋지만 약간 불필요한 연산 있음	더 깔끔하고 빠름

필요하시면, 두 코드의 시간복잡도 비교나, 더 최적화된 버전 (예: for 루프 방식)도 도와드릴 수 있습니다.
또한 다른 문제들도 같은 방식으로 정리해드릴 수 있습니다.