[Python 알고리즘] 백준 11399번 : ATM

문제

• 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 P_i분이다. 줄을 [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과 각 사람이 돈을 인출하는데 걸리는 시간 P_i가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.
• 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P₁ = 3, P₂ = 1, P₃ = 4, P₄ = 3, P₅ = 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분이 된다.

입력

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

# Case 1
5
3 1 4 3 2

출력

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

# Case 1
32

내가 제출한 풀이 - 정답

import sys

n = int(sys.stdin.readline().strip())
p = list(map(int, sys.stdin.readline().strip().split()))
res = 0

p.sort()

for i in range(n):
    res += sum(p[0:i + 1])

print(res)

처음에는 재귀함수를 사용해야 하나 생각을 했지만, sum 함수를 통해 간단하게 풀어냈다.

문제풀이

5명을 받는다는 기준으로 본다.

P_i가 [3, 1, 4, 3, 2]로 들어온다고 본다면,

1. 1번 사람은 3분
2. 2번 사람은 3 + 1 = 4분
3. 3번 사람은 3 + 1 + 4 = 8분
4. 4번 사람은 3 + 1 + 4 + 3 = 11분
5. 5번 사람은 3 + 1 + 4 + 3 + 2 = 13분
6. 총합 = 39분

P_i가 [1, 2, 3, 4, 5]로 들어온다고 본다면,

1. 1번 사람은 1분
2. 2번 사람은 1 + 2 = 3분
3. 3번 사람은 1 + 2 + 3 = 6분
4. 4번 사람은 1 + 2 + 3 + 4 = 10분
5. 5번 사람은 1 + 2 + 3 + 3 + 4 = 12분
6. 총합 = 32분

오름차순으로 정렬하는 것이 절대적으로 좋다. 그래서 우린 P_i를 오름차순으로 정렬한 다음 sum 함수를 통해서 res 변수에 넣어주는 것이다.

Tip

res += sum(p[0:i + 1])

p가 [1, 2, 3, 4, 5]라고 가정한다면,

1. p[0:1] = [1]
2. p[0:2] = [1, 2]
3. p[0:3] = [1, 2, 3]
4. p[0:4] = [1, 2, 3, 4]
5. p[0:5] = [1, 2, 3, 4, 5]

이것을 sum 함수에 넣게 되면, 모든 요소의 합이 반환된다. 그러므로, 따로 p를 잘라내서 sum에 넣는 for문을 돌려 얻는 방식이 아닌 슬라이싱을 통해 쉽게 합을 얻었다.