17212.md

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

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

---

코드 설명

• 이 문제는 동적계획법 거스름돈 문제처럼 생각해서 풀면 된다.
• 다만 주의할 점이 2가지 있는데 첫 번째는 n이 1, 2, 5, 7일 경우 동전의 개수는 1개란 점이며,
• 두 번째로 주의해야 할 점은 n이 17일 경우 7 7 2 1이 아니라 7 5 5로 동전의 개수는 3개란 점이다.
• 아래 코드는 동전의 값만큼 빼준 뒤 1개를 더함으로써 dp[n-coin] + 1을 이용해 dp[n]을 구하는 방식이다.

소스코드

• 메모리 : 34712 KB
• 시간 : 244 ms

n = int(input())
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
coin = [7,5,2,1]

for i in range(1, n+1):
    for j in range(len(coin)):
        if coin[j] <= i and dp[i-coin[j]] + 1 < dp[i]:
            dp[i] = dp[i-coin[j]] + 1

print(dp[n])

오답 노트

• 첫 번째로는 주의해야 할 점중 두 번째를 주의하지 않아 틀렸다. -> 큰 수인 7부터 빼고 봄.
  (n이 17일 경우 3이 나와야 하는데 7부터 빼고 봐서 7 7 2 1 이렇게 4가 나옴)
• 두 번째로는 그냥 문제를 잘못 봤다. 동전의 종류는 1 2 5 7 인데 1 3 5 7 로 봐 문제를 틀렸다..

첫 번째 오답 코드

n = int(input())
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
coin = [7,5,3,1]

for i in range(1, n+1):
    for j in range(len(coin)):
        if coin[j] <= i and dp[i-coin[j]] + 1 < dp[i]:
            dp[i] = dp[i-coin[j]] + 1

print(dp[n])

두 번째 오답 코드

n = int(input())
coin = []  # 7,5,2,1

coin.append(n//7)
n %= 7
coin.append(n//5)
n %= 5
coin.append(n//2)
n %= 2
coin.append(n)

print(sum(coin))