백준 11399번 ATM (JavaScript 풀이)

[백준 11399] ATM 문제 - 그리디 알고리즘

📖 그리디 알고리즘이란?

정의: 매 순간 가장 좋아 보이는 선택을 하는 알고리즘
특징: 한 번 선택하면 되돌리지 않음 (No 후회!)
핵심: "지금 당장 최선 = 나중에도 최선"이라고 가정

일상 예시

동전으로 거스름돈 주기: 1000원을 거슬러 줄 때
× 잘못된 선택: 1원짜리부터 → 1000개 필요
○ 그리디 선택: 500원부터 → 500원 2개 = 총 2개

그리디를 쓸 수 있는 조건

1. 탐욕적 선택 속성: 지역 최적해가 전역 최적해의 일부
2. 최적 부분 구조: 작은 문제들의 최적해로 전체 최적해 구성 가능

---

📌 문제 요약
ATM에서 N명이 줄을 설 때, 모든 사람의 대기시간 합을 최소화하는 문제. 각 사람마다 인출하는데 걸리는 시간이 다르고, 줄 서는 순서에 따라 총 대기시간이 달라진다.

입력: N (사람 수), P₁ P₂ ... Pₙ (각 사람의 인출 시간)
출력: 모든 사람의 대기시간 합의 최솟값

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

---

💡 문제 접근

• 이 문제가 그리디인 이유: 앞사람의 선택이 뒤의 모든 사람에게 영향을 줌
• 핵심 관찰: 앞사람의 인출시간이 뒤의 모든 사람 대기시간에 누적됨
• 그리디 전략: 매 순간 가장 짧은 시간의 사람을 선택
• 증명: 임의의 두 사람 A(a분), B(b분)에서 a < b라면, A→B가 B→A보다 항상 효율적

🔍 그리디 선택 과정

주어진 시간: [3, 1, 4, 3, 2]

1단계: 가장 짧은 시간 선택 → 1분 (전체에 1분씩 5명 = 5분 영향)
2단계: 다음 짧은 시간 선택 → 2분 (전체에 2분씩 4명 = 8분 영향)  
3단계: 다음 짧은 시간 선택 → 3분 (전체에 3분씩 3명 = 9분 영향)
...

이렇게 매번 최선의 선택을 하면 전체 최적해를 얻을 수 있다!

---

📝 풀이 코드 (JavaScript)

const fs = require('fs');
const input = fs.readFileSync(0, 'utf8').trim().split('\n');

const n = +input[0];
const times = input[1].split(' ').map(Number);

// 그리디 전략: 매번 가장 짧은 시간 선택 (정렬)
times.sort((a, b) => a - b);

let answer = 0;
let sum = 0;

for (let time of times) {
    sum += time;        // 현재 사람의 대기시간
    answer += sum;      // 전체에 누적
}

console.log(answer);

---

🔎 풀이 해설

• times.sort(): 그리디 전략을 위한 정렬 (가장 짧은 것부터)
• 반복문에서 각 사람의 대기시간 계산:
  • sum += time: 현재 사람이 기다리는 시간
  • answer += sum: 전체 대기시간에 누적
• 예시: [1,2,3,3,4] → 대기시간: 1+3+6+9+13 = 32분

---

💭 내 생각

• "그리디가 항상 최적일까?" 의문이 들었는데, 수학적으로 증명 가능하다는 게 신기함!
• 일상에서도 그리디 사고를 많이 쓰고 있었구나... (지하철에서 가까운 문 찾기 등)
• 핵심은 "이 선택이 나중에 영향을 주는가?"를 분석하는 것

---

📚 배운 점

• 그리디 vs DP: 그리디는 선택을 되돌리지 않음, DP는 모든 경우를 고려
• 그리디 적용 조건: 지역 최적해가 전역 최적해가 되는 문제에서만 사용 가능
• 증명의 중요성: 그리디가 최적임을 수학적으로 증명할 수 있어야 함
• 정렬의 활용: 많은 그리디 문제에서 정렬이 핵심 전략