[baekjoon] 백준 11399번(파이썬): ATM

문제

11399번: ATM

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

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

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

- 예를 들어, 총 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(1 ≤ N ≤ 1,000)이 주어진다.

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

알고리즘

- 사람의 수를 입력받는다.

- 돈을 인출하는데 걸리는 시간을 입력받아 리스트 변수에 넣는다.

- 각 사람이 돈을 인출하는데 필요한 시간의 합이 최소가 되려면 돈을 인출하는데 걸리는 시간이 적은 순서대로 돈을 인출해야 한다. 따라서 돈을 인출하는데 걸리는 시간을 오름차순으로 정렬한다.

- 돈을 인출하는 시간과 기다리는 시간을 더해주어 기다리는 시간에 넣는다.

- 기다리는 시간을 총 걸리는 시간과 더해주어 총 걸리는 시간에 넣는다.

- 위 과정을 반복한다.

- 마지막에 총 걸리는 시간을 출력한다.

코드

n = int(input())
p = list(map(int, input().split()))
# 돈을 인출하는데 걸리는 시간을 오름차순으로 정렬한다.
p.sort()
# 기다리는 시간
total = 0
# 총 걸리는 시간
result = 0

for i in p:
    # 돈을 인출하는 시간과 기다리는 시간을 더해준다.
    total = i + total
    # 기다리는 시간을 총 걸리는 시간에 더해준다.
    result += total

print(result)

github

junjange/CodingTest