[백준 11399번] ATM - python

문제 링크

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

11399번: ATM

풀이

- dp로 풀이

- 걸리는 시간이 작은 사람부터 실행하면 되므로 data를 오름차순 정렬해준다. 

dp[i] 는 i번째 사람이 돈을 인출하는 데 필요한 시간 

dp[i] = dp[i-1] + data[i]

- dp의 합 출력 

import sys
input = sys.stdin.readline 

n = int(input())

data = list(map(int,input().split()))

data.sort()

dp = [0] * n

dp[0] = data[0]

for i in range(1,n):
  dp[i] = dp[i-1] + data[i]

print(sum(dp))

- 과거에 해당 문제를 푼 적이 있는데 dp로 메모제이션하지 않고 

아래 코드처럼 data[i+1] = data[i+1]+data[i] 로 풀었다. 

- dp로 풀었을 때 68ms가 걸렸고, 아래처럼 풀었을 경우 132ms가 걸린 것으로 보아 dp 훨씬 빠르다

n = int(input())

data = list(map(int,input().split()))

data.sort()

if n == 1:
  print(n)
else :
  for i in range(len(data)-1):
    data[i+1] += data[i]

  print(sum(data))