백준알고리즘 11399번 ATM C#

세부 정보

• 사이트: 백준알고리즘
• 번호: 11399
• 문제명: ATM
• 언어: C#
• 분류: 그리디 알고리즘, 정렬
• 비고: 

 

문제

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

 

출력

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

 

풀이

인출시간 합을 누적 형태로 구하므로 오름차순으로 정렬해야 모든 사람들이 인출하는데 걸리는 시간의 최소값을 구할 수 있다.

첫 번째 사람이 인출할 때는 대기시간이 없으므로 반복문 안이 아니라 반복문 밖이면서 반복문 앞인 곳에서 실행해야 한다.

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

// 사람의 수를 입력한다
int n = Convert.ToInt32(sr.ReadLine());
// 사람마다 인출에 걸리는 시간을 입력받는다
string input = sr.ReadLine();
// 사람마다의 인출시간을 저장할 배열 선언
int[] p = new int[n];
// 사람마다의 인출시간을 공백으로 구분하고 정수로 바꿔서 배열에 넣는다
p = input.Split().Select(int.Parse).ToArray();
// 이전 사람들의 인출시간 합
int temp = 0;
// 모든 사람들의 인출시간 합
int time = 0;
// 배열을 오름차순으로 정렬
Array.Sort(p);
// 첫 번째 사람의 인출
time += p[0];

for (int i = 1; i < n; i++)
{
    // 이전 사람들의 인출시간의 누적합
    temp += p[i - 1];
    // 현재 사용자의 인출시간의 누적합
    time += p[i] + temp;
}

// 모든 사람들의 인출시간 합 출력
sw.WriteLine(time);

sr.Close();
sw.Close();

 

후기

이 문제도 손쉽게 풀렸다. 풀기 전에 가진 마음과 풀고 난 이후의 마음이 달라지는 것 같다. 풀기 전에는 어려울 것 같은 난이도라고 생각하고 지레 겁을 먹기 마련인데 풀고 난 이후에는 너무 쉽고 당연한 문제라서 더 어려운 문제를 찾으려는 것 같다. 이러면서 역량이 향상되고 더 많은 보상을 받기 마련이다. 어려운 것을 해결하는 과정은 재미와 활력을 불어넣어 준다. 이러니 월급루팡은 쉬운 것만 하다가 재미도 잃고 갈 곳도 줄어들게 되는 제 무덤 파기라고 생각한다.