[BOJ] 14916 - 거스름돈 (🥈 실버 5티어)

사용 언어: Python3

문제

거스름돈

풀이

나의 풀이 - DP

N = int(input())
coin = [2, 5]

# ✅ dp[i]: i원을 거슬러주는데 사용된 동전의 최소 개수
dp = [50001] * (N+1) # min()을 적용할 것이기 때문에 최댓값으로 초기화 (N은 최대 100000 -> 모두 2원일 때 최댓값은 50000)
dp[0] = 0 # ✅ 0원을 거슬러주는데 사용되는 동전의 수는 0개

for c in coin:
    for j in range(c, N+1):
        dp[j] = min(dp[j-c]+1, dp[j]) # ✅ c 동전을 사용한다고 가정했을 때: dp[j-c]+1 (+1 은 c 동전을 사용한거니까 동전 개수 1개 추가)

print([-1, dp[N]][dp[N] != 50001])

• 테스트 케이스: 성공
• 제출 결과: 성공

다른 풀이 - 그리디

참고

N = int(input())
cnt = 0
while N>0:
    if N % 5 == 0:
        cnt += N//5
        break
    N -= 2
    cnt += 1

print([cnt, -1][N<0])

• 테스트 케이스: 성공
• 제출 결과: 성공

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기