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

-Code

n = int(input())
dp = [0, 1, 1, 2, 2, 1, 2, 1]
for i in range(8, n + 1):
    c = min(dp[i - 7], min(dp[i - 5], min(dp[i - 2], dp[i - 1]))) + 1
    dp.append(c)
print(dp[n])

처음에 그리디로 풀려고 봤더니 풀 수 없는 문제여서 직접 손으로 각 수마다 값이 어떻게 나오는지 확인해보니 뒤죽박죽이어서 연관성을 찾기 어려웠으나 값 - 7에 1을 더하면 몇몇 값이 비슷한 것을 알게 되었습니다. 하지만 10이나 17같이 값이 다른 값도 나오게 되어 이 부분에서 막혔습니다. 그래서 검색을 해보니 그냥 -7한 것처럼 모든 동전 종류의 수만큼을 다 빼서 +1 한 것 중 가장 작은 것을 고르면 되는 문제여서 해결했습니다.