BOJ 14916

Input

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

1	n = int(input())

Output

거스름돈 동전의 최소 개수를 출력한다.

만약 거슬러 줄 수 없으면 -1을 출력한다.

DP

최소 거스름돈 개수를 구해야 하기 때문에, 큰 수인 5로 거스름돈을 나누기 시작해야 한다.

그리고 5로 나눈 나머지를 2로 나누었을 때 0이 되면 그게 정답이 되고, 0이 아니면 5를 줄이고 2를 늘려봐야 한다.

그래도 답이 안 나오면 거슬러 줄 수 없는 경우(e.g. 1)이므로 -1을 출력하면 됨.

for five in range(int(n/5), -1, -1):
  coin = five
  money = n - (5 * five)
  if money % 2 == 0:
    coin += int(money / 2)
    print(coin)
    exit()
    
print(-1)

Better Solution

DP 문제인 만큼, 형식에 맞게 풀어보자.

Default
- 매번 sys.stdin.readline 을 치기보다, 기본처럼 input() 으로 간단하게 처리하기 위해 아래와 같이 세팅한다.
1
2
import sys
input = sys.stdin.readline
1
2
3
4
5
6
7
n = int(input())

# 나머지
num = n % 5

# 동전 개수
count = 0
Exception : 5보다 작은 수 중 2로 나눌 수 없는 1이나 3 일 경우, 2나 5로 나눌 수 없기 때문에 -1을 출력한다.
1
2
3
if n == 1 or n == 3:
print(-1)
exit(0)
5로 먼저 나눈 후, 나머지가 2로 나눠지면 5로 나눈 몫과 2로 나눈 몫을 더하여 출력한다.

몫을 int(n / 5) 와 같이 처리하지 말고, python의 // 를 활용하자!
1
2
3
elif num % 2 == 0:
print(n // 5 + num // 2)
exit(0)
나머지가 2로 나눠떨어지지 않는 경우, 5의 몫을 -1하고 (나머지에 5를 더하여) 다시 2로 나눈 몫과 5로 나눈 몫을 더하여 출력한다.
1
2
3
else:
print((n // 5 - 1) + (num + 5) // 2)
exit(0)