[백준/C++] 11399 ATM (S3)

유형	난이도	완료일	링크	특이사항
그리디	실버3	23/03/26	https://www.acmicpc.net/problem/11399

 

 

내 코드

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	
	int arr[1000] = {};
	for(int i=0;i <n; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr+n);
	
	int sum = 0;
	int gross = 0;
	for(int i=  0; i< n; i++)
	{
		sum = sum + arr[i];
		gross = gross + sum;
	}
	
	cout << gross;
}

  자기 앞의 사람이 일을 다 볼 때까지 뒷사람이 기다려야 하므로 가장 시간이 오래 걸리는 사람이 맨 뒤로 가야한다. 일을 처리하는 것에만 걸리는 시간의 총 합은 같겠지만 각 사람이 기다려야 하는 시간의 총합은 줄 서는 순서에 따라서 바꿀 수 있고 이 줄 서는 시간을 최소로 줄이는 경우를 구하는 문제다.

현재 상황에서 무조건 최선인 “시간이 적게 걸리는 사람”을 선택하는 방식으로 해결하므로 그리디 알고리즘이라고 할 수 있겠다.