99클럽 코테 스터디 14일차 TIL / 그리디

✏️ 문제

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

 

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S5

✅ 소요 시간: 14분

✅ 권장 시간: 1시간 15분

 

💡 풀이

1) 문제 유형 파악

어제 올린 TIL에서 그리디 문제의 예시로 동전 문제를 언급했는데 오늘 바로 관련된 문제가 나왔다.

 

2) 아이디어 흐름

① 조건문 설정: n이 5의 배수일 때

5원짜리를 많이 써야 동전 수를 최소로 만들 수 있기 때문에 n이 5의 배수인 경우와 아닌 경우로 조건을 나눴다. n이 5의 배수면 정답은 n을 5로 나눈 몫이 된다.

 

② 조건문 설정: n이 5의 배수가 아닐 때

주어진 입출력 예시처럼 n이 5의 배수가 아닌 경우를 잘 처리하는 게 중요하다고 생각한다.

 

입출력 예시 1이 매우 좋은 예시라고 느낀 게 단순히 n을 5로 나눈 몫만 생각한다면 5원짜리를 두 개까지 쓸 수 있지만, 5원을 두 개 쓰면 나머지가 2로 나눠 떨어지지 않아 거슬러 줄 수 없게 된다.

 

그래서 n이 5의 배수가 아닐 때는 n을 5로 나눴을 때의 나머지가 짝수인지 홀수인지 확인하는 조건문을 추가해줬다.

 

n을 5로 나눴을 때 나머지가 짝수라면 5원짜리는 n//5개까지 사용 가능하고 그렇지 않으면 5원짜리는 (n//5)-1개까지 사용 가능하다.

 

③ 예외 처리

n이 1이거나 3이면 어떻게 해도 거스름돈을 줄 수 없기 때문에 이 때만 -1을 출력해주면 된다. 11, 13 이런 값들은 못 거슬러주게 생겼지만 5, 2를 조합하면 거슬러 줄 수 있다는 게 뽀인트

 

3) 구현

n = int(input())

answer = 0

if n == 1 or n == 3:
    answer = -1
else:
    if n%5 == 0:
        answer = n//5
    else:
        if (n%5)%2 == 0:
            q = n//5
        else:
            q = (n//5)-1
            
        answer += q
        
        n -= q*5
        
        answer += n//2

print(answer)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 없음

❗ 배운 점

• 오늘은 기억에 남는 배운 점이 없었음