알고리즘 (1) 썸네일형 리스트형 SORT 백준 11399번 ATM 문제출처 : https://www.acmicpc.net/problem/11399문제 핵심 ATM 앞에 N명이 줄을 설 때 각 사람이 기다린 시간의 총합이 최소가 되도록 줄을 다시 세우고, 그 최소 총합을 구하는 문제1. 왜 “정렬”이 답일까?사람 돈 뽑는 데 걸리는 시간 Pi①3분②1분③4분④3분⑤2분앞사람이 끝나야 뒷사람이 시작할 수 있으므로,짧게 걸리는 사람부터 세우면 뒤사람이 덜 기다립니다.결국 Pi를 오름차순으로 정렬하면 총기다림 시간이 최소가 됩니다.( 증명: “그리디 교환 논법” – 긴 사람·짧은 사람 순서를 바꾸면 항상 더 좋아짐 )2. 최소 총합 계산 절차정렬 : P = [1, 2, 3, 3, 4]앞사람까지의 누적시간을 차례로 구함첫 사람 1두 번째 1 + 2 = 3세 번째 1 + 2 + .. 이전 1 다음