✓

태그:

15. 그리디 알고리즘 CLASS 3 ESSENTIAL

ATM기에서 여러 사람이 돈을 뽑을 때 각 사람이 기다려야 하는 시간의 합의 최소값을 구하는 문제입니다. 사람마다 돈을 뽑는 데에 시간이 다르게 걸리는데, 뒤에 있는 사람은 앞에 있는 모든 사람이 돈을 뽑을 때까지 기다려야 합니다. 각 사람의 돈을 뽑는 시간을 a[i]라고 하면 i번째 사람이 돈을 뽑으려면 \(\sum_{k=1}^{i}a[k]\)만큼 필요합니다. 이 값을 최소로 만드는 것이 목표입니다. 그렇게 하려면 사람을 돈을 뽑는 시간이 적게 걸리는 사람을 앞에 배치하면 됩니다. 증명은 아래에 첨부하겠습니다. 이제 규칙에 따라 사람마다 걸리는 시간을 구하고, 이를 모두 더하여 출력하면 됩니다.

증명

각 사람마다 돈을 뽑는 데에 걸리는 시간 a가 있습니다. 문제의 규칙에 따라 각 사람이 돈을 뽑는 데까지 필요한 시간 b를 아래와 같이 정의합니다. $$ b_i=\sum_{k=1}^{i}a_k $$ 이제 문제에서 구하려는 시간 c를 정의합니다. $$ c=\sum_{k=1}^{n}b_k=\sum_{k=1}^{n}\sum_{i=1}^{k}a_i=\sum_{k=1}^{n}(n+1-k)a_k $$ 수열 a의 j번째 원소인 a_j와 그 다음 원소인 a_j+1의 대소 관계에 따라 c의 값이 어떻게 바뀌는지 알아봅시다. c는 아래와 같이 됩니다. $$ c=\sum_{k=1}^{n}(n+1-k)a_k=na_1+(n-1)a_2+...+(n+1-j)a_j+(n-j)a_{j+1}+...+a_n $$ 어떤 두 값을 a_j과 a_j+1에 할당해야 한다면, 자명하게도 a_j와 a_j+1 중 a_j에 넣는 것이 c 값을 더 줄일 수 있을 것입니다. 작은 값이 a_j+1에 들어가면 c 값이 할당할 두 값의 차이만큼 늘어납니다. 따라서 작은 값이 앞으로 와야 합니다. 이 방법을 버블 정렬처럼 인접한 원소끼리 적용하여 재배열시킨다면 a는 증가수열, 즉, 정렬된 상태가 될 것입니다. 따라서 주어진 돈 뽑는 시간 수열을 정렬하면 총 필요한 시간을 최소로 만들 수 있습니다.

소스 코드

언어	코드	시간
Python 3	코드(Github) / 코드(백준)	2020-04-01 23:13:46

---