BaekJoon 11399 ATM

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

소스결과 1988 KB / 0 ms

출처 Baekjoon

언어 C++ 17

분류 그리디 알고리즘

 

설명

인행의 ATM 기기의 사용시간을 최소로 구하는 알고리즘

 

그리디 알고리즘이라 분류하고, 알고리즘은 정렬로 짜고, 결과값을 위해서는 DP를 사용한다.

정렬하고 전 사람이 사용하기까지 걸린 시간에 내 시간을 더한다.

다 합친다.

 

알고리즘

1. 사람들의 사용 시간을 오름차순으로 정렬한다.

2. 이전 사람까지의 사용 시간에 내가 사용할 시간을 더한다.

3. 모든 사람이 사용한 시간을 더해 출력한다.

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int main()
{
	int timeTable[1000];
	int n;
	int sum = 0;

	cin >> n;

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

	// Selection Sort

	for (int i = 0; i < n; i++)
	{
		int min = i;
		for (int j = i; j < n; j++)
			if (timeTable[min] > timeTable[j])
				min = j;
		swap(timeTable[i], timeTable[min]);
	}
	
	for (int i = 1; i < n; i++)
		timeTable[i] += timeTable[i-1];

	for (int i = 0; i < n; i++)
		sum += timeTable[i];

	cout << sum;

	return 0;
}