14916 거스름돈

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

# 거스름돈 2,5로만
# 동전 개수 최소로
# 거스름돈은 n임
# 최소 동전의 개수는?

# 문제 풀이
# 5로 먼저 나누고 2로 나눈다

N = int(input())
results = []
coins = [5,2]

# 5를 최대한 사용 가능한 횟수 K
K = N//5

if K == 0 :
    temp = N // 2
    if N % 2 > 0 :
        print(-1)
    else :
        print(temp)

else :
    min_val = 1e9
    for i in range(0,K+1):
        # 5원의 개수 : i
        two_temp = (N - 5*i) // 2 # 2원의 개수 : two_temp
        if (N - 5*i) % 2 == 0 : # 딱 계산 가능하면
            min_val = min(min_val,i+two_temp)
            # results.append(i+two_temp)
    if min_val == 1e9 :
        print(-1)
    else :
        print(min_val)

3. 생각 및 풀이

생각

이 문제는 기초적인 그리디 문제이다. 생각보다 구현해야할게 조금 있다. 조건을 항상 잘 살펴야한다.

문제 풀이

이 문제는 5원을 몇개 사용하는지에 따라 거스름돈이 딱 맞아 떨어질 수도, 아닐 수도 있고 최소의 동전의 수를 찾을 수도, 없을 수도 있음을 명심하자.

이걸 파악한다면 어려운 문제는 아니다.

5원을 사용할 수 있는 최대 개수를 파악하고 0개부터 시작해서 5원을 사용하고 남은 돈을 2원으로 나눴을 때, 나눠 떨어지지 않으면 거스름돈을 거슬러 줄 수 없다. 나눠 떨어지더라도 최소의 개수를 찾아야 하므로 min_val을 이용해서 최소 개수를 항상 기억하도록 한다. 반복문이 종료된 후, min_val이 갱신되지 않았으면, 나눠 떨어지는 수가 없는 것이므로 -1을 반환한다.