사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분
사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라짐
ex) 총 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)
출력
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력
시간 제한: 1초
메모리 제한: 256 MB
"""
입출력 예시)
n = 5
3 1 4 3 2
-> 32
"""
## 의사코드 ##
# pi 리스트를 오름차순 정렬 -> 작은 값부터
# for i in range(n):
# minimum += pi[i]
첫 번째 시도
n = int(input()) # 사람의 수
pi = list(map(int, input().split()))
# pi 리스트 오름차순 정렬
pi.sort()
minimum = 0 # 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값
for i in range(n):
minimum += pi[i]
print(minimum)
-> 그냥 마지막 사람(Pn)이 돈을 인출하는데 필요한 시간만 구해져서 틀림
과정 확인
"""
1
3
6
9
13
"""
통과한 코드
n = int(input()) # 사람의 수
pi = list(map(int, input().split()))
# pi 리스트 오름차순 정렬
pi.sort()
wait_time = 0 # 각 사람이 돈을 인출하는데 필요한 시간
minimum = 0 # 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값
for i in range(n):
wait_time += pi[i]
minimum += wait_time
print(minimum)
-> 각 사람이 돈을 인출하는데 필요한 시간인 wait_time을 따로 구함
과정 확인
"""
1
4
10
19
32
"""
다른 풀이
n = int(input()) # 사람의 수
seconds = list(map(int, input().split()))
minimum = 0
seconds.sort()
for i in range(n):
for j in range(i + 1):
minimum += seconds[j]
print(minimum)
-> 이중 for문으로 seconds 리스트에서 인덱스 0부터 i까지의 값을 더한 값이 minimum이 됨