[알고리즘] 백준 11399 ATM

문제

인하은행에는 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)

 

출력

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

 

 

나의 풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let cnt = Number(input[0]);
let array = input[1].split(" ").map(Number);
let sortedArray = array.sort((a,b)=>a - b);
let total = 0;
for (let i = 0; i<cnt; i++){
    total = total + (cnt-i) * sortedArray[i]
   
}

console.log(total)

 

이번 문제에선 나의 풀이방식과 다른사람의 풀이 방식이 크게 다르지 않았다. 다만 나는 숫자로 형변환 후 sort를 했는데, 이 과정에서 좀 시간이 더 걸렸다고 한다..

 

어쨌거나 풀이 방식을 설명해본다.

 

일단 문제에서 알 수 있듯, 돈을 인출하는데 필요한 시간이 적은사람이 먼저 인출하는게 유리하다.

 

예를들어, 세명이 있는데 인출하는데 걸리는시간이 각 1, 5, 10분이 걸린다고 하자.

 

10, 5, 1 순서로 기다리게 된다면

최초 10분동안 인출, 그다음 사람은 10분 기다렸다 5분 인출, 그 다음사람은 15분 기다렸다 1분 인출을 하여 총 41분이 생긴다.

 

하지만 1, 5, 10 순서로 기다리게 된다면

최초 1분 인출, 그 다음사람은 1분 기다렸다 5분 인출, 그 다음사람은 7분 기다렸다가 10분 인출로 총 24분의 합이 생긴다.

 

실제 ATM이 동작한 시간은 같겠지만, 오래걸리는 사람을 앞에 배치한다면 그만큼 다른사람들은 기다리지 않아도 되는 시간을 더 기다리게 되면서 발생하는 문제이다. 즉, 사람수가 많을수록 차이가 심해진다.

 

어쨌든 위처럼 개념을 잡고 나면 문제는 쉬워진다.

배열 [a, b, c, d]가 있다고 가정하자.

현재 문제를 보면 

a+(a+b)+(a+b+c)+(a+b+c+d) 형태를 띄고 있다. 즉 n개의 배열이 있다면

n*a + (n-1)b + (n-2)*c ....  이런 답을 찾게 될 것이다.

 

따라서 for문을 통해 배열의 길이만큼 반복문을 돌리고, 반복문 안에서는 n-i 를 배열의 순서대로 곱한값의 누적합을 구하면 되는 것이다.