TIL 37 | ATM 그리디알고리즘+DP (백준 11399 python)

Gom·2021년 3월 15일
0

Algorithm

목록 보기
14/48
post-thumbnail

문제 바로가기

문제요약

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값

조건

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방식이 미세하지만 더 짧은 시간이 소요되었다. 프로그램이 실행될 때마다 서버 컴퓨터의 상태에 따라 약간의 오차가 발생할 수 있다고도 하니 이 정도의 차이는 비교하는 것에 의미를 둘 수 없어보인다.

profile
안 되는 이유보다 가능한 방법을 찾을래요

0개의 댓글