👉 문제 링크
그리디. 알고리즘 첫 공부할 때 엄청 풀었었는데 기억이 가물가물해서 제일 쉬운 문제로 시작하려고 골라보았다. 아자아자
👉 풀이
핵심 아이디어는 "대기 시간 최소" -> 인출 시간이 적은 순으로 정렬 필요
반복문을 돌면서 대기 시간을 합한 것이 답
첫 번째로 생각한 방법은
변수 두개를 사용하여 하나는 현재 순서까지의 대기 시간을 더하는 것, 두 번째는 모든 사람들의 대기 시간을 저장을 위해 만들어야겠다는 아이디어였다.
min, pre = 0,0
# min : 모든 사람들이 인출하는 데 소요 시간
# pre : 현재 순서의 사람이 인출할 때까지 드는 시간
for i in range(n):
min += pre + p[i]
pre += p[i]두 번째 방법은
굳이 두개가 필요할까?
하나의 변수에 처음부터 현재 순서까지의 합을 계속 더해나가면 되겠다.는 생각
ans = 0
for i in range(n+1):
ans += sum(p[:i])결론은 둘 다 맞는 방법이었다.
👉 전체 코드
1)
import sys
input = sys.stdin.readline
n = int(input())
p = list(map(int,input().split()))
p.sort()
min, pre = 0,0
# min : 모든 사람들이 인출하는 데 소요 시간
# pre : 현재 순서의 사람이 인출할 때까지 드는 시간
for i in range(n):
min += pre + p[i]
pre += p[i]
print(min)2)
import sys
input = sys.stdin.readline
n = int(input())
p = list(map(int,input().split()))
p.sort()
ans = 0
for i in range(n+1):
ans += sum(p[:i])
print(ans)