백준_14916 (거스름돈_실버5_그리디)

RostoryT·2022년 7월 3일
0

DP and Greedy

목록 보기
3/12

메모

메모한것

2와 5로만
동전 개수가 최소가 되도록
출력할 것 : 거스름돈이 n일 때, 최소 동전의 개수

13원일 때, 5원 1개 + 2원 4개 = 총 5개가 된다

방법이 없으면 -1 출력

알고리즘

n = 13
money = [2, 5]
ans = 0
while n>0:
    
    ### 이런식으로 병렬로 처리하자
    
    if n // 5 > 0:   # n을 5로 나눌 수 있을 때
        ans = ans + (n // 5) - 모든 경우의 수를 해볼 수 있도록 변수하나 생성해주자
        n = n % 5
        
    if n // 2 > 0:
        ans += n // 2
        n = n % 2
        
    if n == 0:
        break
    else:
        n = 13   # 모든 경우의 수 해볼 수 있도록 원상복구 시켜주기

시복

변수

m : 원래대로 돌릴 수 있도록하는 정답값 원본
stopword : 0,1,3은 어떻게 해도 안나오는 값이므로 미리 전처리
minus : 처음에 5로 빼보고 안되면 5 하나씩 빼면서 모든 경우의 수 해볼 수 있게


솔루션 코드 - 내가 푼

n = int(input())
m = n
money = [2, 5]
ans = 0
stopword = [0,1,3]

minus = 0

while n>=0:
    if n in stopword:
        ans = -1
        break
    
    if n // 5 > 0:
        ans += (n // 5) - minus
        n = (n % 5) + (minus * 5)
        
    if n // 2 > 0:
        ans += (n // 2)
        n = n % 2
        
    if n == 0:
        break
    elif n > 0:
        n = m
        ans = 0
        minus += 1
        
print(ans)



솔루션 코드 - 다른 블로그1

import sys
input = sys.stdin.readline

n = int(input())

dp = [-1] * (n+8)

dp[2]=1
dp[4]=2
dp[5]=1
dp[6]=3
dp[7]=2
dp[8]=4

for i in range(9, n+1):
    dp[i] = min(dp[i-2], dp[i-5])+1

print(dp[n])

솔루션 코드 - 다른 블로그2

  1. 일단 5로 나눈 나머지가 0이면 5의 배수이므로, 몫을 answer로 하고 끝내버려
  2. 만약 5로 안나눠지면 2로 계속 나누면서 answer++ 해줘 (=2원 개수 하나씩++해주는거)
    2-1. 다음 while에서 5의 배수가 나오면 몫을 answer에 더해주고 끝내면 됨
  3. 근데 2원씩 뺐는데 음수 되어버리면 거슬러줄 수 없는 경우임
n = int(input())

cnt = 0
i = 0

while True:
    if n % 5 == 0:   # 5의배수이면 or 2로만 거슬러주고 n이 0이된경우 
        cnt += n//5  #5로나눈 몫이 정답 - 끝!
        break
    else:
        n -= 2       #5의배수가 아니면 2백원씩 뺴면서 5로 나누어떨어지는것이 나오도록
        cnt += 1

    if n < 0:        # 2백원씩 뺏더니 음수가 되버린경우 --> 거슬러줄수 없을을 의미함 
        break
        
        
print(-1) if n < 0 else print(cnt)

profile
Do My Best

0개의 댓글