[백준] 11399번, ATM - Python

들어가기 앞서

학기 중에 전공과목을 병행하느라 포스팅을 거의 하지 못했다. 방학을 맞아 그동안 풀었던 문제들을 복습해보고 새롭게 푸는 문제들을 포스팅 할 계획이다. 저번학기 자료구조를 수강하며 더 많은 알고리즘을 접할 수 있던 것이 좋은 경험이 되었다.

 

 

ATM문제는 그리디 알고리즘에서 기초가 되는 문제이다. 

 

그리디 알고리즘이란 이름에서도 알 수 있듯이 탐욕스러운 알고리즘이다. 즉, 지금 당장 우리가 하는 최선의 선택이 전체로 봤을 때도 최선의 선택인 경우 그리디 알고리즘을 이용할 수 있다.

 

여기서 내가 어렵게 느꼈던 점은 지금 당장의 선택이 이후 결과에 영향을 미치는 상황일 때 최선의 선택이 보장 될 수 있느냐였다. 이것이 그리디 문제가 어려운 이유이고, 앞으로 다양한 문제를 풀어보며 더 고민을 해봐야 할 것 같다.

 

문제 이해

1대의 ATM이 존재한다.

 

N명의 사람들이 줄을 서서 자신의 차례를 기다린다.

 

사람들은 1번부터 N번까지 번호가 매겨진다.

 

P1, P2, ..., PN 으로 각 사람들이 ATM 기기를 이용하는 시간이 주어진다.

 

모든 사람들이 ATM 기기를 이용해야할 때 총 시간의 최솟값을 구하는 것이 문제이다.

 

예를들어, N=5이고 

[3,1,4,3,2] 의 소요 시간이 주어졌을 때

최소 시간이 나오는 순서는 

2번사람 -> 5번사람 -> 1번사람 (4번이 와도 됨) -> 4번사람 (1번이 와도 됨) -> 3번사람 이고, 

그때 총 시간의 최소는

1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4) = 1 + 3 + 6 + 9 + 13 = 32분 이 된다.

 

 

해설

사실 내가 문제를 풀 때 그리디라는 생각은 크게 하지 않았다.

 

먼저 기본적으로 앞사람의 시간은 결국 뒷사람에게 누적되기 때문에 총 시간을 최소로 만드려면 소요 시간이 작은 사람이 앞 순서로 와야한다는 점이었다. 나중에 생각해보니 이것이 그리디의 개념일 것이라는 생각이 들었다. 결국 매 순간 최종 목표를 위한 최선의 선택을 하기 때문이다.

 

조금 더 집중해서 봐야 할 특징이 누적이다.

위에서 본 예제를 각각의 사람별로 ATM 기기를 쓸 때까지 기다리는 시간으로 나눠서 써보면,

 

2번 사람: 1

5번 사람: 1 + 2

1번 사람: 1 + 2 + 3

4번 사람: 1 + 2 + 3 + 3

3번 사람: 1 + 2 + 3 + 3 + 4

 

이런식으로 조금 더 직관적으로 누적되는 과정이 보인다.

누적의 관점에서 총 소요 시간을 다시 써보면,

1*5 + 2*4 + 3*3 + 3*2 + 4*1 으로 최종식을 쓸 수 있다.

 

이것을 일반화 시키면 각각의 사람들의 소요 시간을 오름차순으로 정렬한 뒤, for문을 이용해서 각각의 소요 시간에 N, N-1, N-2, ..., 1 까지 차례대로 곱한 뒤 더하는 과정이다.

 

즉 어떠한 N이 들어오더라도 해결이 가능해지는 것이다.

 

 

실제 코드

n = int(input())
time = list(map(int, input().split()))

time.sort(reverse=True)

result = 0
for i in range(1, n+1):
    result += i * time[i-1]

print(result)

 

time 리스트를 내림차순으로 정렬한 이유는 

 

오름차순으로 정렬하게 되면, for 문에서 0번 리스트에 있는 가장 작은 소요 시간에 N부터 곱해 나가야하는데

 

인덱스와 곱하는 수를 하나는 증가 하나는 감소시켜야해서 이 방향을 통일하기 위해 내림차순으로 정렬했다.

 

내 코드로 풀면 백준 채점에서 시간이 108ms로 나오는데, 가장 빠른 풀이(96ms)를 보니 time을 그냥 오름차순 정렬로 두었다. reverse를 하지 않고 for문에서 (N-i)의 처리를 해주는 것이 파이썬 연산에서는 더 빠르게 처리가 되는 것 같다.

 

 

시간 복잡도

총 주어진 시간이 1초이고 N의 범위는 1 <= N <= 1000 이다.

 

1초에 2000만번의 파이썬 연산, 그리고 백준에서 주어지는 5배의 여유 시간까지 고려하더라도 1억번의 연산 안에 해결하면 된다.

 

N이 1000이기 때문에 대략 N 제곱까지 가능하다고 생각하면 된다.

 

우리의 코드는

sort() 함수 O(NlogN),

for문 O(N) 시간이 걸리므로 

 

전체 시간은 NlogN이 될 것이다. 

 

따라서 시간 내에 해결 가능하다.

 

 

사실 알고리즘을 반복 연습하는 과정이라 어떤 알고리즘을 써야하는지 알고 있었다. 하지만 어떤 문제를 처음 봤을 때는 해당 문제가 그리디인지, DP인지, 이분탐색을 써야하는지 등 적절한 알고리즘을 떠올리기가 어려웠던 것 같다. 해당 알고리즘을 왜 사용해야하는지 심도있게 고민하는 과정이 나중에 큰 도움이 될 것 같다.