백준알고리즘 11399번 ATM

문제링크

 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

그리디 알고리즘을 이용한 것으로 인출하는데 걸리는 시간이 적은 사람부터 정렬을 하면 답은 간단하게 구해진다. 
정렬을 하게 되면 {1,2,3,3,4} 
첫 번째 사람은 1분
두 번째 사람은 (1+2)분
세 번째 사람은 (1+2+3+분
네 번째 사람은 (1+2+3+3)분
다섯 번째 사람은 (1+2+3+3+4)분이다.

풀었던 알고리즘 문제중에서 가장 쉬웠다.

기분이 좋다 하하.....

개발을 하면서 알고리즘을 쓰질 않아 왜 필요한지 의문이 들었는데.. 요즘들어 절실하게 필요하다는 것과 공부해야한다는 중요성을 느낀다.

하나하나.. 정복해나가야지