[백준 11399번] ATM

문제 링크 >> https://www.acmicpc.net/problem/11399

 

 

📋 문제

인하은행에는 ATM이 1대밖에 없다.

지금 이 ATM앞에 N명의 사람들이 줄을 서있다.

사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는 데 걸리는 시간은 Pi분이다.

 

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다.

예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자.

 

[1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다.

2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다.

3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다.

4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다.

이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

 

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분 만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다.

각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다.

이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

 

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는 데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

 

👉 입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

 

 

👈출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

 

📝 풀이

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

time = [arr[0]]
for i in arr[1:]:
  time.append(time[-1]+i)

print(sum(time))

 

문제를 처음 봤을 때 생각난 풀이는 돈을 뽑는데 시간이 제일 적게 걸리는 사람부터 돈을 뽑게 하면 합이 최솟값이 나오지 않을까? 였다.

 

사람의 수 n과 각 사람이 돈을 인출하는데 걸리는 시간이 들어있는 arr을 입력받았다.

이때 arr은 돈을 인출하는데 가장 시간이 적게 걸리는 것 순으로 오름차순 정렬한다.

 

이후 time이라는 리스트를 선언하는데 이때 arr[0]의 값을 time에 넣어둔다.

arr의 1번째 요소부터 for문으로 순회하며 time에 time[-1] + i의 값을 넣는다.

이 과정을 거치면 time에는 돈을 뽑는 순서 별로 각 사람들이 돈을 뽑는데 걸리는 시간이 들어간다.

 

따라서 모든 사람이 돈을 뽑는 시간의 합을 구하기 위해 time의 sum 값을 출력한다.