[백준 11399 파이썬] ATM (실버3, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = int(input())
time = list(map(int, input().split()))
time.sort()

for idx in range(1, N):
    time[idx] += time[idx-1]
print(sum(time))

풀이 요약

1. 구조를 잘 살펴보면, 각 사람들이 기다린 시간을 모두 합한 것을 구하는 문젠데, 그 합을 잘 살펴보면 1번째 사람 기다린 시간은 N번, 2번 째 사람 기다린 시간은 N-1번, N번 째 사람이 기다린 시간은 1번 더해진다. 즉, 사람이 오른쪽에 있을수록 그 사람의 기다린 시간이 합해지는 수가 적어지므로, 큰 수를 오른쪽에 둬야한다. 그래서 시간 리스트를 오름차순 정렬하고, 그 리스트를 가지고 바로 모든 사람들의 기다린 시간의 합을 구하는 for를 작성하면 된다.

배운 점, 부족했던 점

• 되게 쉬운 문제였다. 그런데 DP로 접근해보려고도 했는데 쉽지가 않다. 일단 공부 효율을 위해 너무 오래 붙잡지않고 넘어갈 것이지만, 나중에 한 번 시간, 공간복잡도 상관없이 DP로도 풀어보고싶다.