[BOJ/Python] 11399 : ATM

정나영·2023년 5월 14일
0

👉 문제 링크

그리디. 알고리즘 첫 공부할 때 엄청 풀었었는데 기억이 가물가물해서 제일 쉬운 문제로 시작하려고 골라보았다. 아자아자

👉 풀이

핵심 아이디어는 "대기 시간 최소" -> 인출 시간이 적은 순으로 정렬 필요
반복문을 돌면서 대기 시간을 합한 것이 답

첫 번째로 생각한 방법은
변수 두개를 사용하여 하나는 현재 순서까지의 대기 시간을 더하는 것, 두 번째는 모든 사람들의 대기 시간을 저장을 위해 만들어야겠다는 아이디어였다.

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)

0개의 댓글