📖 문제 링크
https://www.acmicpc.net/problem/11399
📃 문제 설명
그리디 알고리즘을 이용하는 문제로
각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력하면 된다.
사람들의 시간은 기다리는 시간 + 자신이 걸리는 시간이 된다.
👨💻 문제 풀이
생각해보면 쉬운 문제이면서 까다롭다.
일단 sort를 이용해 정렬하여 인출을 가장 빨리 하는 사람부터 실행하면 된다.
하지만 그냥 sort로 정렬하고 +해버리면 기다리는 시간은 포함되지 않는다.
그래서 빈 list에 각자의 시간을 저장하고 합쳐주었다.
N = int(input())
time = 0
each_time = list()
people = list(map(int, input().split()))
people.sort()
for user in people:
time += user
each_time.append(time)
result = sum(each_time)
print(result)append와 sum을 사용하여 시간, 공간 복잡도가 올라갔다.
그냥 0으로 된 변수 2개를 두어 하나씩 저장하는 방법도 있었다..😨
복잡도를 줄이기 위해 머리를 많이 굴려야겠다ㅠ
2021.08.22
backend-developer