[그리디 알고리즘] ATM

예제 입력 1

5

3 1 4 3 2

예제 출력 1

32

 

 

- 그리디 알고리즘으로 접근하고자 할 때는 반례를 찾고, 최적이 맞다고 생각되면 증명이 필요하다.

- 정답은 적게 걸리는 시간으로 정렬하여 푼다.

- 증명은 아래와 같다.

: t1 ~ t5는 1~5번 사람이 돈을 인출하는데 걸리는 시간이며, P1 ~ P5는 각 사람이 돈을 인출 완료하기까지 기다려야 하는 시간, 각 번호는 t가 작은 순으로 오름차순으로 정렬되어있다고 가정.

: P1 = p1

: P2 = p1 + p2

: P3 = p1 + p2 + p3

: ....

: P5 = p1 + ... + p5

 

Psum = 5*p1 + 4*p2 + ... + p5

 

따라서 p1이 작을수록 유리하다.

#include <stdio.h>

constexpr int MAX_COUNT = 1000;

int people[MAX_COUNT];
int N;

void swap(int data[], int a, int b)
{
	int temp = data[a];
	data[a] = data[b];
	data[b] = temp;
}

int partition(int data[], int start, int end)
{
	int index = start;

	for (int i = start; i < end; i++)
	{
		if (data[i] <= data[end])
		{
			swap(data, i, index);
			index++;
		}
	}

	swap(data, index, end);
	return index;
}

void qsort(int data[], int start, int end)
{
	if (start >= end) return;

	int pivot = partition(data, start, end);
	qsort(data, start, pivot - 1);
	qsort(data, pivot + 1, end);
}

int main(void)
{
	int result = 0;
	int waitTime = 0;

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		scanf("%d", &people[i]);

	qsort(people, 0, N - 1);

	for (int i = 0; i < N; i++)
	{
		result += (people[i] + waitTime);
		waitTime += people[i];
	}

	printf("%d\n", result);

	return 0;
}