백준 11399 [ATM]

문제링크: https://www.acmicpc.net/problem/11399

 

♣ 문제정리

사람의 수 N

i번째 사람이 돈을 인출하는 데 걸리는 시간 : 입력값 (1,2,3...N)

순서를 아무렇게나 할 수 있음

각 사람이 돈을 인출하는 데 걸리는 총 시간의 최소값: 출력값

 

 

♣ 코드 작성 전 생각할 거리

경우의 수: N!

총 시간이 최소인 경우의 순서를 알 필요는 없다.

가장 오래 걸리는 사람을 조금 더하고, 가장 적게 걸리는 사람을 가장 많이 더해야지 총 합이 최소

-> 정렬!

 

 

 

♣ 코드 작성

총 시간을 구하려면 배열에서 각 원소에 왔을 때 처음부터 그 순서까지를 계속 더해야 한다

i:0 -> 0

i:1 -> 0, 1

i:2 -> 0,1,2

i:3 -> 0,1,2,3

i:4 -> 0,1,2,3,4

 

이것에 충실하게 코드를 작성했다

n = int(input())

# fetch하는 time 넣을 리스트
f_times = list(map(int, input().split(' ')))

f_times.sort()

sum = 0
k=1

while(k <= n):
    for i in range(0, k):
        sum = sum + f_times[i]
    k += 1

print(sum)

 

 

하지만, 조금만 더 생각해 보면,

sum이나 k라는 변수를 따로 만들지 않아도 배열을 순차적으로 갱신해주는 방법도 있다!

우리가 구해야 하는 것은 소요시간들의 합이기 때문에 각 배열의 원소들을 이전 원소들을 더한 합으로 바꿔준다. 

=> 순차적으로 각 원소는 (자신의 값 + 이전 원소값)으로 바꿔준다.

그리고 바뀐 배열들의 합을 구해도 같은 답이 나오게 된다.

for i in range(1, n):
    f_times[i] += f_times[i-1]
print(sum(f_times))

코드길이도 많이 줄었고 시간은 거의 절반으로 줄어듬을 알수 있다!!!!!!

memoization을 사용한 방법

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술! 동적 계획법의 핵심

 

 

코드를 작성하러 들어가기 전에 어떻게 작성할 건지를 확실하게 하는 게 시간을 절약하는 데 중요하다!

즉, 코드 작성보다는 문제를 분석하는 데에 시간을 더 투자하자