[백준 14916번] [🥈5] 거스름돈 (python)

백준 사이트 링크

문제

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

손님이 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을 출력한다.

예제 입력 1

13

예제 출력 1

5

예제 입력 2

14

예제 출력 2

4

---

풀이

정수 n이 주어졌을 때, 5원짜리 동전과 2원짜리 동전만을 가지고 n원을 만들 때, 필요한 동전 개수의 최솟값을 구하는 문제로 만약 n원을 만들 수 없다면 -1을 출력해야 한다.

우선 5원짜리 동전을 가능한 한 많이 사용해야되고 만약 n이 5의 배수이면, 5원짜리 동전만을 사용하여 원하는 금액을 만들 수 있다. 이 경우, 필요한 동전의 개수는 n // 5 이다.

만약 n이 5의 배수가 아니면, 5원짜리 동전을 사용할 수 없으므로 2원짜리 동전을 사용해야 한다. 이때는 n에서 2원씩 빼면서 5원짜리 동전을 사용하는 것보다 가능한 한 많이 2원짜리 동전을 사용한다. 만약 이 과정에서 n이 음수가 되면 원하는 금액을 만들 수 없다는 것이므로 -1을 출력한다.

이렇게 하면 최소한의 동전 개수로 원하는 금액을 만들 수 있다.

코드

ver(1) - Greedy 사용

# 정수 n을 입력받습니다.
n = int(input())

# 필요한 5와 2의 최소 개수를 구하는 변수 result를 초기화합니다.
result = 0

# 무한 루프를 돌면서 5로 나누어 떨어지는지 확인합니다.
while True:
    # 만약 5로 나누어 떨어진다면, result에 (n // 5)를 더한 후 결과를 출력하고 루프를 빠져나갑니다.
    if n % 5 == 0:
        result += (n // 5)
        print(result)
        break
    # 5로 나누어 떨어지지 않는다면, n에서 2를 빼고 result에 1을 더합니다.
    else :
        n -= 2
        result += 1
    # 만약 n이 0보다 작아진다면, 5와 2로 나타낼 수 없으므로 -1을 출력하고 루프를 빠져나갑니다.
    if n < 0:
        print(-1)
        break

ver(2) - Dynamic Programming 사용

# 정수 n을 입력받습니다.
n = int(input())

# DP 테이블 dp를 생성합니다.
# 여기서 dp[i]는 i번째 사다리를 올라가는 최소 이동 횟수를 의미합니다.
dp = [-1] * (n+8)

# 초기값을 설정합니다.
dp[2]=1
dp[4]=2
dp[5]=1
dp[6]=3
dp[7]=2
dp[8]=4

# DP를 실행합니다.
for i in range(9,n+1):
    dp[i] = min(dp[i-2],dp[i-5]) + 1

# n번째 사다리를 올라가는 최소 이동 횟수를 출력합니다.
print(dp[n])