백준 2720 : 세탁소 사장 동혁 (그리디) **

www.acmicpc.net/problem/2720

2720번: 세탁소 사장 동혁

거스름돈 문제

거스름돈 = 5달러 이하

쿼터(0.25$), 다임(0.1$), 니켈(0.05$), 페니(0.01$)

손님이 받는 동전의 갯수를 최소로!

 

Input : # of test case  = T
           # 거스름 돈 ( T번 )

 

Output : # of 쿼터, # of 다임, # of 니켈, # of 페니

              ( Q, D, N, P)

 

풀이:

       0.25*Q + 0.1*D + 0.05*N + 0.01*P = 거스름돈, 

       단, Q+D+N+P = 최소

       금액이 큰 순으로 나눠주면 된다. 

 

def solve(t): # t는 거스름돈
    Q, D, N, P = [25,10,5,1]
    ans_Q = t//25
    t -= 25*ans_Q
    
    ans_D = t//10
    t -= 10*ans_D
    
    ans_N = t//5
    t -= 5*ans_N
    
    ans_P = t//1
    
    return [int(ans_Q), int(ans_D), int(ans_N), int(ans_P)]
        
        
    

if __name__=='__main__':
    T = int(input())
    problems = []
    for _ in range(T):
        problems.append(int(input()))
    for t in problems:
        ans = solve(t)
        print(*ans) # 각 금액마다 solution을 print

 

 

---------------------오답 풀이 ------------------

문제에서 달러($)로 설명했길래, 달러에 맞게 식을 짰더니 틀렸다.

IDE에 돌려보니 소숫점 계산에서 문제가 있었다.

0.24-0.1*2 =0.04가 나와야 하는데, 0.03999999999999998 이 나온다.

float 형태의 유효숫자 문제여서, 반올림을 쓰면 해결될 것 같았지만, 안전하게 정수형으로 바꿔서 풀었다. 

def solve(t): # t는 거스름돈
    Q, D, N, P = [0.25,0.1,0.05,0.01]
    ans_Q = t//0.25
    t -= 0.25*ans_Q
    print(t)
    ans_D = t//0.1
    t -= 0.1*ans_D
    print(ans_D,t)
    ans_N = t//0.05
    t -= 0.05*ans_N
    print(ans_N,t)
    ans_P = t//0.01
    print(t)
    return [int(ans_Q), int(ans_D), int(ans_N), int(ans_P)]
        
        
    

if __name__=='__main__':
    T = int(input())
    problems = []
    for _ in range(T):
        problems.append(int(input()))
    for t in problems:
        ans = solve(t/100)
        print(*ans) # 각 금액마다 solution을 print

 

다른 풀이에서 (ryuwhale95 님) divmod(p,n) 을 알게 됐다.

p = q*n + r에서 (q,r) 을 return 함.