언어 전공자의 NLP 로그
[그리디] ATM - 백준 11399번 본문
https://www.acmicpc.net/problem/11399
11399번: ATM
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
www.acmicpc.net
n = int(input())
numbers = list(map(int, input().split()))
wait_time = 0
total = 0
while numbers:
wait_time += numbers.pop(0)
total += wait_time
print(total)
- 해당 문제에서는 매 순간의 최적해가 최솟값이다.
- 따라서 최솟값을 찾아 pop으로 꺼내어 매번 wait_time에 더해주고, total은 각각의 wait_time의 합이 된다.
- 애초에 선택을 최솟값으로 뽑기 때문에 이 경우에는 나머지 경우를 생각할 필요가 없다.
- '매 선택이 최적의 해'라는 그리디 원칙에 충실하면 굉장히 간단한 문제였다.
'코딩테스트' 카테고리의 다른 글
| [큐] 최솟값 찾기 - 백준 11003 (0) | 2023.09.29 |
|---|---|
| [그리디] 설탕 배달 - 백준 2839 (0) | 2023.09.19 |
| [구름톤 챌린지] 구름 찾기 깃발 (0) | 2023.08.22 |
| [구름톤 챌린지] 이진수 정렬 (0) | 2023.08.18 |
| [큐] 프로세스 (0) | 2023.08.17 |