728x90
문제
https://www.acmicpc.net/problem/11399
문제는 길지만, 요약하자면 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하면 되는 것이다.
풀이
import sys
# 문제 입력받기
N = int(input())
lines = list(map(int, sys.stdin.readline().split()))
lines.sort()
sum_list = [0]
# 누적합 구하기
for line in lines:
tmp = line + sum_list[-1]
sum_list.append(tmp)
print(sum(sum_list))
먼저, 인출 시간이 적은 사람 순으로 정렬을 한 후, 각 사람마다 걸리는 시간을 합한다.
즉,
입력이 3 1 4 3 2 로 주어질 때,
1 2 3 3 4 순으로 정렬한 후,
1 : 1분 소요
2 : 1+2=3분 소요
3 : 1+2+3=6분 소요
3 : 1+2+3+3=9분 소요
4 : 1+2+3+3+4=13분 소요
가 되며,
모두 돈을 인출하는데 걸리는 시간의 합은 1+3+6+9+13=32분이 된다.
다른 사람 풀이
좀 더 쉽게 누적합을 구한 풀이를 발견하여 함께 남겨본다.
N = int(input())
P = list(map(int, input().split()))
P.sort()
answer = 0
for i in range(1, N+1):
answer += sum(P[:i])
print(answer)
728x90
'코딩테스트 > PYTHON' 카테고리의 다른 글
[백준][PYTHON] 13305번 주유소 (0) | 2024.06.05 |
---|---|
[백준][PYTHON] 1541번 잃어버린 괄호 (0) | 2024.05.30 |
[백준][PYTHON] 1931번 회의실 배정 (1) | 2024.05.23 |
[프로그래머스][PYTHON] Lv. 1 덧칠하기 (0) | 2024.04.29 |
[프로그래머스][PYTHON] Lv. 1 추억 점수 (0) | 2024.04.12 |