📌문제 링크
💡 문제 풀이
기다리는 시간이 최소가 되게 하려면 시간이 가장 짧은 사람이 먼저 줄을 서게 하면 된다.
Pi를 입력받고 sort()한 순서대로 시간을 더해주면 된다.
단, 인덱스 0부터 i까지 누적한 시간을 계속 더해줘야 하는데 이걸 어떻게 제일 효율적으로 더할 수 있을지가 좀 고민됐다.
📋코드 - 리스트 슬라이싱
처음에 리스트 슬라이싱을 사용해서 누적합을 구했다.
# 11399 ATM
import sys
n = int(input())
p = list(map(int, sys.stdin.readline().split()))
p.sort() # 돈 인출 시간이 적은 순서대로 정렬
result = 0
for i in range(n):
# i번째까지 슬라이싱한 배열의 합을 더함
result += sum(p[:i+1])
print(result)
그런데 굳이 매번 슬라이싱+sum함수를 써가며 해결하지 않아도 되겠다는 생각이 들었다...
📋코드 - 누적합을 저장하는 변수 사용
그냥 변수 하나 선언해서 시간을 계속 더해주면 그게 누적합이 되고, 그걸 result에 또 더해줬다.
# 11399 ATM
import sys
n = int(input())
p = list(map(int, sys.stdin.readline().split()))
p.sort() # 돈 인출 시간이 적은 순서대로 정렬
result = 0
s = 0
for i in range(n):
# 0번째부터 i번째까지 시간 더함
s += p[i]
# i번째까지 누적한 합을 더함
result += s
print(result)
이 방법이 조금 더 빠르긴 했는데 크게 시간차이는 나지 않았다..
(사진에서 위가 변수 사용 방법, 아래가 리스트 슬라이싱 방법)
N이 1000까지라서 그런걸지도..
sum의 시간복잡도가 O(n)이니까 더 큰 수까지 받으면 차이가 더 날지도 모르겠다
