백준 11399 atm

atm (백준 11399)

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

최솟값을 구하는 문제로
문제에서 이미 ‘이 방법보다 더 효율적인 방법은 없다’라는
부분이 주어졌기에 greedy를 적용할 수 있다고 생각하였다

하나의 선택을 한 후, 다음 선택을 하며
각각의 선택 과정이 반복되기에
최적 부분구조를 만족한다

가장 작은 값부터 고르는 것이, 곧 최선의 선택이므로
탐욕 선택 속성을 만족한다

정렬 후, 반복문을 한번 돌기에 아주 빠르긴 하다

Code

import sys

inp = sys.stdin.readline

num = int(inp().strip())

vals = list(map(int,inp().split()))

vals.sort()

times = 0
sumTimes = 0

for i in range(num):
    times += vals[i]
    sumTimes += times

print(sumTimes)

해결 아이디어

1. 짧은 순서대로, 줄을 세워야 모든 사람이 돈을 인출하는데 필요한
   시간의 합이 최소가 된다
   
2. list를 정렬하여 가장 대기 시간이 짧은 순서대로 정렬시킨다
   
3. 이전 시간의 합과 현재 대기 시간을 합쳐 times를 구한다
   
4. 반복문에 같이 넣어 총 시간합을 구한다