[python] BOJ 11399 ATM

백준 11399번 ATM 문제 풀이

문제를 읽어보자.

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

여기서 각 사람이 돈을 인출하는데 필요한 시간은 각 사람이 인출하는데까지 기다린 시간 + 인출하는데 걸리는 시간이다.

즉 인출하는데 걸리는 시간은 고정값이기때문에, 사람들이 줄 서 있는 순서를 적절히 배치해서 기다리는 시간을 줄이는게 핵심일 것 이다.

 

풀이

문제 풀이를 위한 알고리즘을 생각해보자.

단순하게 문제에 제시된 예시만 보더라도 쉽게 발견할 수 있는 것이 있다.

앞에서 더 해진 숫자가 계속 더해진다는 것. 즉 쉽게 말해서, 상대적으로 앞 순서에 위치한 사람 중에 인출에 오래걸리는 사람이 있다면 그 사람보다 뒷 순서에 위치한 모두가 기다리게 되는 것이다.

이렇게 직관적으로 생각해보아도 인출에 걸리는 시간이 적은순으로 오름차순 정렬해서 배치해야된다는 사실을 알 수 있고,

식을 살펴보아도, 계산과정에서 누적합이 적용된다는 것을 쉽게 알아차릴 수 있다.

앞 사람의 대기시간+인출 시간이 뒷 사람의 대기시간이 되기때문에, 인출 시간이 누적돼서 더 해진다. 따라서 이렇게 계산해도 인출시간이 적은 순으로 정렬해서 배치해야된다는 것을 알 수 있다.

 

3 1 4 3 2 의 경우는 1 2 3 3 4 로 정렬해서 계산한다.

 

첫번째 사람의 경우 대기 시간 + 인출시간 ==> 0 + 1 = 1

두번째 사람의 경우 1 + 2 = 3

세번째 사람의 경우 3 + 3 = 6

네번째 사람의 경우 6 + 3 = 9

마지막 사람의 경우 9 + 4 = 13

따라서 총 합인 1 + 3 + 6 + 9 + 13 = 32 이다

 

위의 전개식을 보면, 이전 사람의 인출에 필요한 시간(대기시간 + 인출시간)이 다음 사람의 대기시간이 되는 것을 볼 수 있다.

그것에 맞게 코드를 작성하면 되는 간단한 문제이다.

 

 

간단한 문제이지만, 그리디 알고리즘을 이해할 수 있는 문제였다.