백준 11399번 ATM (C#)

오늘은 백준 11399번 ATM 문제를 풀면서 겪은 시행착오와 깨달음을 정리해본다.

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

문제 설명

N명의 사람이 줄을 서서 ATM을 이용하려고 한다.
각 사람이 돈을 인출하는 데 걸리는 시간이 주어진다.
사람들이 줄을 서는 순서에 따라 각 사람이 기다리는 시간의 합이 달라지므로,
기다리는 시간의 총합이 최소가 되도록 줄을 세우려고 한다.

처음에 헷갈렸던 점

문제에 P1 = 3, P2 = 1... 식으로 예시가 나와 있어서,
나는 이걸 보고 숫자 1은 3분, 숫자 2는 1분 처럼 사람과 시간을 매핑해야 하는 줄 알았다.
그래서 switch문으로 1이면 3분, 2면 1분… 이렇게 처리해봤는데, 결과가 계속 이상했다.

하지만 알고 보니:

• 3 1 4 3 2 ← 이 입력값은 사람 번호가 아니라

• 그냥 각 사람이 인출하는 데 걸리는 "시간"을 나열한 것이었다.

즉, 처음부터 사람 번호는 중요하지 않고, 인출 시간의 정렬만이 핵심이었다.

해결 방법

인출 시간 배열을 오름차순으로 정렬

누적합을 구한 후, 전체를 더해주면 된다

작성 코드

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace backjoon
{
    internal class Program
    {
        static void Main()
        {
            int inputCount = int.Parse(Console.ReadLine());
            int[] times = Console.ReadLine().Split().Select(int.Parse).ToArray();

            Array.Sort(times); // 오름차순 정렬

            int total = 0;
            int sum = 0;

            for (int i = 0; i < inputCount; i++)
            {
                sum += times[i]; // 현재 사람까지의 누적 시간
                total += sum;    // 총합에 더함
            }

            Console.WriteLine(total);

        }
    }
}

깨달은 점

문제를 읽을 때 이 숫자가 뭘 의미하는지 반드시 명확하게 해석해야 한다.

예시 설명이 혼란을 줄 수 있으니, 문제 의도와 실제 입력값의 의미를 잘 구분하자.

최소 대기 시간을 만들기 위해선, 작은 값부터 처리하는 그리디(탐욕법)을 떠올리면 된다.

마무리

처음에 사람 번호와 시간을 매핑하는 방식으로 착각해서 삽질을 좀 했지만, 문제의 본질을 파악하고 나니 정렬 + 누적합이라는 익숙한 패턴이었다.
문제를 더 깊게 읽고 해석하는 연습이 필요하다는 걸 다시 느꼈다.