[JAVA / 자바] 백준(BOJ) 11399번 - ATM (실버 3)

 문제 

인하 은행에는 ATM이 1대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, 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분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분 만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는 데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 인출하는 데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

---

 입력 

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는 데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

---

 출력 

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

---

 

---

 문제 접근 방법 

이번 문제는 ATM 기기를 이용하는 사람들이 걸린 시간의 총합을 구하는 문제이다.

따라서 인출하는데 필요한 시간의 합이 최소가 되어야 하므로 다음과 같은 상관관계를 알고 있다면 이 문제는 단순한 정렬 문제라는 것을 알게 된다.

바로 앞사람이 인출을 끝내야 그다음 사람의 인출을 시작할 수 있다는 것이다.

그렇다면 i번째 사람이 인출하는데 필요한 시간 = 1 ~ i-1번째 사람의 인출시간 총 합 + i번째 사람의 인출시간이다.

 

이래도 이해가 잘 안 되어 다음 상황을 예시로 들어보면,

(i번 사람의 인출시간 = Ti로 표현)

1번 사람의 인출이 끝나는 시간

 >>> T1

2번 사람의 인출이 끝나는 시간

 >>> T1 + T2

3번 사람의 인출이 끝나는 시간

 >>> T1 + T2 + T3

...

n번 사람의 인출이 끝나는 시간

 >>> T1 + T2 +... + Tn

 

따라서, 사람들이 인출하는데 걸린 총시간은

T1 + (T1 + T2) +... + (T1 + T2 +... + Tn)  = T1 * n + T2 * (n-1) +... + Tn*1이다.

따라서 인출하는 데 걸리는 시간이 적은 순으로(오름차순으로) 정렬하여 총합을 구해주면 그 값이 답이 된다.

---

 JAVA 코드 풀이 

 코드 실행 결과 

---

 후기 

이번 문제는 단순히 오름차순으로 정렬 후 총합을 구하면 됐던 문제로 큰 어려움 없던 문제였다.

---

 문제 원본 

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

11399번: ATM

 알고리즘 분류 

• 그리디 알고리즘
• 정렬