[백준 2720] 세탁소 사장 동혁 Python greedy 그리디 알고리즘

 

백준 2720번 문제 세탁소 사장 동혁

greedy 알고리즘 문제

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

2720번: 세탁소 사장 동혁

 

문제 풀이

중고등학생 때 풀던 동적 최소 개수 문제랑 똑같다.

괜히 영어동전으로 만들어놨다고 쫄 필요 없다.

거슬러줘야 하는 값을 m에 배열로 담고

현재 m을 coin의 큰 값부터 나누어

몫은 출력할 문자열에 추가,

나머지는 원래 m에 다시 저장하기를 동전 종류 수 만큼 반복한다.

 

 

해답 코드 Python

#백준 2720 세탁소 사장 동혁 greedy
from sys import stdin

#입력, 사용할 데이터 배열
T = int(stdin.readline())
m = [int(stdin.readline()) for _ in range(T)]
coin = [25, 10, 5, 1]

#케이스 수 만큼 반복. m을 coin의 큰 값부터 나누어 몫은 출력할 문자열에 추가, 나머지는 원래 m에 다시 저장 반복
for i in range(T) :
    countString = ""
    for j in range(4) :
        countString += str(m[i]//coin[j]) + " "
        m[i] %= coin[j]

    #출력
    print(countString)

 

---

Comment

• 입력받기

[입력 for _ in range(반복수)]

이렇게 하면 원하는 형태의 입력을 반복해서 받고 하나의 배열로 저장할 수 있다.

입력에는 stdin.readline() 같은 입력도, 0 같은 그냥 값도 가능