백준 11399번 ATM [그리드 알고리즘]

백준 11399번 ATM

백준 11399번 ATM 문제는 사용자들마다 사용 시간이 다르고, 그 사용시간에 따라서 다음 사용자의 대기시간 + 이용시간이 점점 누적된다.
이에 모든 사람들이 최소한의 시간값을 구하는 문제이다.

 

[문제풀이과정]

1.  사람들마다 ATM을 이용하는 시간이 정해져 있고, 각 사람들의 순서에 따라서 전체 사용자의 사용시간이 결정된다.

2. 적게 걸리는 사람들이 앞에 있을 수록 전체 사용시간은 줄어든다. (정렬이 필요하다)

3. 대기시간 + 현재 사용자의 이용시간

4. 이 문제에서 중요한 것은 정렬을 할 경우, 오름차순이 최소 값을 보장하는가

 

예)

• [1,5] 일 경우 1분 + 6분 = 7분
• [5,1] 일 경우 5분 + 6분 = 11분

 

[코드]

total_count = int(input())
times = sorted(map(int,(input().split())))

current = 0
result = 0
for t in times:
    current += t
    result += current
print(result)

 

시간 복잡도는 내장함수 sorted()는 내부적으로 Timesort 사용한다. O(N log N) + O(N) = O(N log N)