백준 - 11399번(그리디)

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

11399번: ATM

 

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))

ans = [0]
arr.sort() #가장 시간이 적게 걸리는것 부터 먼저처리 하도록 오름차순 정렬

for i in range(n):
    ans.append(ans[i] + arr[i])

print(sum(ans))

 

import sys

n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))

ans = 0
arr.sort()
for i in range(n):
    ans = ans + arr[i]*(n-i)

print(ans)

 

위 두 개는 원리는 동일하나 연산과정만 조금 다른 동일한 알고리즘이다.

운영체제에서 CPU 스케줄링을 배울 때 배웠던 SJF(Shortest Job First)와 완전히 동일한 문제다.

현실에서도 동일한 경우가 있는데 나는 5분짜리 일을 처리하러 은행에 왔는데 앞사람이 1시간 걸리는 일을 처리하면 나는 1시간을 기다려야 한다. 물론 먼저 온 사람이 먼저 일처리를 받는 것이 옳지만, 효율의 관점에서는 그렇지 않다.

짧은 일들을 먼저 하고 가장 오래 걸리는 일을 나중에 하면 결론적으로 평균적으로 기다리는 시간은 감소한다.

첫 번째는 누적 값을 계속 더해주고 마지막에 최종적으로 더해주는 것이고 이를 좀 더 간단하게 수학식으로 적어보면 두 번째 코드가 된다.

arr [i]에 존재하는 값은 최종적으로 (n-i)번 더해질 것이기 때문이다.