[BOJ/백준] 17212번 달나라 토끼를 위한 구매대금 지불 도우미 (Python 파이썬)

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

17212번: 달나라 토끼를 위한 구매대금 지불 도우미

 

문제

달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 불법이다. 예를 들어, 17원을 지불할 때 7원짜리 동전 1개와 5원짜리 동전 2개로 지불해야 합법이고, 7원짜리 동전 2개와 2원짜리 동전 1개, 1원짜리 동전 1개로 지불해도 17원이 되지만, 총 동전의 개수가 4개가 되어 최소 개수가 아니므로 불법이다.

지불 금액을 입력받아 합법이 되는 동전 개수를 출력으로 내어주는 프로그램을 작성해보자.

입력

첫 번째 줄에 달나라 토끼가 지불해야하는 금액 N(0 ≤ N ≤ 100,000)이 주어진다.

출력

첫 번째 줄에 달나라 토끼가 합법적으로 낼 수 있는 동전의 개수를 출력한다.

예제 입력 1 

12

예제 출력 1 

2

예제 입력 2 

21

예제 출력 2 

3

힌트

지불 금액	합법 지불	불법 지불(예)
12원	7원 x 1개 + 5원 x 1개	5원 x 2개 + 2원 x 1개
17원	7원 x 1개 + 5원 x 2개	7원 x 2개 + 2원 x 1개 + 1원 x 1개
21원	7원 x 3개	7원 x 2개 + 5원 x 1개 + 2원 x 1개

 

---

풀이

우선 i원의 금액을 지불할 최소의 동전 개수을 담을 dp 리스트를 선언해줍니다.

현재 동전의 종류는 1,2,5,7원 입니다. dp[i]에 최소의 동전 개수가 담기기 위해서는 아래의 작업을 실시합니다.

dp = [1e9]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    # dp[i]에 최소값이 담기도록 한다.
    # 순서는 1원 -> 2원 -> 5원 -> 7원
    # 어짜피 모두 검사하여 고려하기 때문에 최솟값이 담긴 후에야 다음 인덱스로 넘어간다.

    dp[i] = dp[i-1] + 1

    if i >= 2:
        dp[i] = min(dp[i], dp[i-2] + 1)
    if i >= 5:
        dp[i] = min(dp[i], dp[i-5] + 1)
    if i >= 7:
        dp[i] = min(dp[i], dp[i-7] + 1)

가장 먼저 (1) 1원을 사용하는 경우을 우선 dp[i]에 대입합니다. 이는, 2,5,7원의 경우 i값이 작아서 동전을 사용 못하는 경우가 있으니, 최소한 1원을 사용하기 위함입니다.

그 다음 (2) 조건문을 통해 2, 5, 7원을 사용할 수 있는 지 확인한 후, dp[i]에 대입합니다. 
이때, 무작정 사용하는 것이 아니라 동전을 사용하는 경우와 사용하지 않는 경우를 비교하여 더 작은 쪽을 대입합니다.

 

 

최종적인 코드 구현은 아래와 같습니다.

Code

import sys
input = sys.stdin.readline
N = int(input())
# i원의 금액을 지불할 최소의 동전 개수
dp = [1e9]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    dp[i] = dp[i-1] + 1

    if i >= 2:
        dp[i] = min(dp[i], dp[i-2] + 1)
    if i >= 5:
        dp[i] = min(dp[i], dp[i-5] + 1)
    if i >= 7:
        dp[i] = min(dp[i], dp[i-7] + 1)

print(dp[-1])