-
2720. [Python]세탁소 사장 동혁Python_알고리즘/Bronze III 2023. 2. 3. 23:47
1. 문제
https://www.acmicpc.net/problem/2720
2720번: 세탁소 사장 동혁
각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 128MB
- Greedy Algorith(탐욕 알고리즘)
3. 파이썬 코드
N = int(input()) # 돈 단위가 1.00$ 달러가아닌 100으로 표현되서 각 돈에 100을 곱한 리스트 생성 money = [25, 10, 5, 1] for _ in range(N): # 들어온 input 돈을 money 리스트를 반복해가며 몫을 출력하고 나머지를 payback 에 넣어줌 payback = int(input()) for i in money: print(int(payback//i), end=" ") payback %= i print()
4. 문제를 풀고난 후 생각
- 문제에서 주어진 돈의 단위가 정수 단위여서 정수를 소수로 변환해서 문제를 풀었었다. => 왕창 틀렸음
- 문제에 주어진 값들을 정수 그대로 사용하고 돈의 단위를 0.25 => 25 소수에서 정수단위로 변경해서 풀었다.
- 외에는 Greedy Algorithm을 푸는 방식대로 큰 돈의 단위부터 값을 구해가며 나머지를 반환해주는 방식으로 문제를 해결함.
5. 문제를 푸는데 도움이 되는 지식
- Greedy Algorithm(탐욕 알고리즘)