Baekjoon 11399 ATM JAVA

해당 문제는 DP를 사용하여 쉽게 해결하였다.

https://www.acmicpc.net/problem/11399

11399번: ATM

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2011399

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

ATM 기기로 돈을 뽑을 때 걸리는 최소한의 시간을 구하는 문제로 돈을 뽑을 때는 앞사람의 걸린 시간만 큼 기다린 시간을 더해줘야 하며 최종 모든 사람이 기다린 수를 더해 최소한의 시간을 구하면 된다.

​

i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 예를 들어, 총 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분이 된다.

​

처음에 배열에 P 값을 저장하고 오름차순으로 정렬을 한 뒤 dp 배열에 이제 각 걸리는 시간을 계산해 주고 모두 더해 출력해 주면 쉽게 해결 가능하다.