[99클럽 코테 스터디 14일차 TIL] 거스름돈 - 백준 14916

오늘도 Greedy이다.

굉장히 쉽게 풀렸다.

 

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개를 
주어야 동전의 개수가 최소가 된다.

[입력]
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

[출력]
거스름돈 동전의 최소 개수를 출력한다.
만약 거슬러 줄 수 없으면 -1을 출력한다.

풀이 접근

사실 같은 이름의 다른 문제를 풀어본 적이 있어 굉장히 쉬웠다.

우선 5원으로 얼마나 처리할 수 있는지 확인해야 한다.

n / 5 -> 5원으로 낼 수 있는 5원의 개수

5원을 낼 수 있을 만큼 낸 이후 나머지를 내기 위해 몇 개의 2원이 필요한지 찾으면 된다.

(n % 5) / 2

하지만! 나머지가 홀수라면?? 문제가 생긴다.

 

문제의 예시로 살펴보자.

거스름돈이 13원인 경우, 위의 공식대로 라면 다음과 같은 상황이 발생한다.

13 / 5 = 2
13 % 5 = 3 <- 2원으로 나눠내기 불가능!

해결법은 간단하다.

5원 하나를 빼고 나머지를 2원으로 내면 된다.

홀수 + 홀수는 반드시 짝수이기 때문에 2원으로 내는 것이 항상 가능하다.

13 / 5 = 2
13 - (5 * 2) = 3 <- 2원으로 나눠내기 불가능!

5원 1개를 뺌
13 - (5 * (2 - 1)) = 8 <- 2원으로 나눠내기 가능!

단, 이는 거스름돈이 5원 이상일때만 가능한 방법이기 때문에

1,3원은 어떻게 하더라도 5원과 2원만을 이용해서 해결할 수 없다.

let n = Int(readLine()!)!
var result = -1
// 1원이나 3원이면 불가능
if !(n == 1 || n == 3) {
    // ((n % 5) % 2 == 0) -> 5로 나눈 나머지가 홀수인지 확인
    // (n / 5) + ((n % 5) / 2) -> 5로 나눈 나머지가 짝수라서 나머지가 2원으로 해결가능한 경우
    // (n / 5) - 1 + ((n % 5) + 5) / 2 -> 5로 나눈 나머지가 홀수라서 나머지가 2원으로 해결 불가능한 경우
    result = ((n % 5) % 2 == 0) ? (n / 5) + ((n % 5) / 2) : (n / 5) - 1 + ((n % 5) + 5) / 2
}
print(result)

최종 코드 - Swift

let n = Int(readLine()!)!
var result = -1
if !(n == 1 || n == 3) {
    result = ((n % 5) % 2 == 0) ? (n / 5) + ((n % 5) / 2) : (n / 5) - 1 + ((n % 5) + 5) / 2
}
print(result)

최종 코드 - Python3

n = int(input())
result = -1
if not (n == 1 or n == 3):
    result = (n // 5) + ((n % 5) // 2) if ((n % 5) % 2 == 0) else (n // 5) - 1 + ((n % 5) + 5) // 2
print(result)

Conclusion

Greedy도 기본적인 개념은 이해했지만 어려워지면 풀기가 어렵다.

난이도를 조금씩 높여가야겠다.