문제요약
각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값
조건
1. 각 사람마다 인출하는데 걸리는 시간이 다르다.
2. ATM기가 한 대이므로 앞 사람들이 다 처리할때까지 기다려야 한다.
3. 줄을 서는 순서에 따라 필요한 시간의 합이 달라진다.
접근방식
1. 처리시간이 적게 걸리는 사람부터 처리하면 갈수록 누적되는 대기시간을 줄일 수 있다.
2. 무조건 작은 값부터 처리해도 최적의 해를 구할 수 있다.
3. 즉 그리디 알고리즘을 사용해도 되는 문제에 해당한다.
4. 시간의 합을 구한다. 이전 값을 이용하여 누적시킨다는 점에서 dp방식이 떠올랐다. dp방식과 그렇지 않은 경우 두 가지로 구현해보자.
코드설계
1. 사람 수를 입력받고 다음 줄에는 각 사람의 인출 처리시간 p를 한 번에 입력받아 리스트에 저장한다.
2. 오름차순으로 정렬한다.
3. 리스트의 앞에 위치한 원소를 시작으로 합산 시간을 누적해간다.
3-1. 전체 로직은 동일하나 시간의 합을 구하는 방식을 dp방식 버전과 그렇지 않은 경우로 만들어보았다.
DP 방식으로 합산한 코드
1차 > 틀렸습니다!
import sys
r=sys.stdin.readline
n = int(r())
p_list = sorted(list(map(int, r().split())))
dp = []
for p in p_list:
if p_list.index(p) == 0: -------- 🐞
dp.append(p)
else:
dp.append(dp[-1]+p)
print(sum(dp))오답원인 : 🐞 index(p)는 리스트의 첫번째 p가 오는 자리만을 반환하므로 첫번째 숫자와 동일한 값이 존재할 때 누적연산없이 p 그대로를 dp에 추가하고 말았다.
수정 후 정답코드
import sys
r=sys.stdin.readline
n = int(r())
p_list = sorted(list(map(int, r().split())))
dp = [p_list[0]]
for p in p_list[1:]:
dp.append(dp[-1]+p)
print(sum(dp))변수를 활용해 합산한 코드
import sys
r=sys.stdin.readline
n = int(r())
p_list = sorted(list(map(int, r().split())))
sum = 0
rst = 0
for p in p_list:
sum+=p
rst+=sum
print(rst)결과 비교
윗 줄은 dp방식 채점 결과, 아래는 일반 변수를 사용하여 값을 누적한 결과이다.
리스트 자료를 가져와 계산에 사용하고 append 과정을 거치기에 더 긴 시간이 걸리지 않을까 예상하였는데 dp방식이 미세하지만 더 짧은 시간이 소요되었다. 프로그램이 실행될 때마다 서버 컴퓨터의 상태에 따라 약간의 오차가 발생할 수 있다고도 하니 이 정도의 차이는 비교하는 것에 의미를 둘 수 없어보인다.
