[백준] 11399번 : ATM(탐욕 알고리즘)- 파이썬[Python]

choisanghyun 2022. 1. 16. 23:13

728x90

문제

11399번: ATM

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

www.acmicpc.net

풀이

import sys
N=int(sys.stdin.readline())
N_list=list(map(int,sys.stdin.readline().split()))
N_list.sort() #오름차순 정렬
nn=0 #누적 계산용
solve=0 #답 출력용
for i in N_list:
  nn+=i
  solve+=nn
print(solve)

탐욕 알고리즘을 활용한 문제이다.

시간이 덜 걸리는 순서대로 줄을 세워야 필요한 시간이 최소값이 된다.

줄을 서는 순서에 따라 걸리는 시간을 오름차순으로 정렬을 한뒤 누적용 변수(nn)와 답 출력용 변수(solve)를 만들어

누적용 변수에 누적값을 쌓은 뒤 solve변수에 더해서 답을 내면 된다.