[C++] 백준 11399번 ATM

1. 문제이해

11399번: ATM (acmicpc.net)

11399번: ATM

 

사람의 수와 각 사람들이 돈을 인출하는데 걸리는 시간이 주어진다.

사람들이 차례대로 줄을 서서 돈을 인출할 때,

각 사람들이 돈을 인출하는데 필요한 시간의 합의 최소값을 구하는 것이 목표이다.

 

 

 

2. 문제풀이

 

문제가 어디서 많이 본듯이 익숙하다 싶었는데..

학부 알고리즘때 배웠던 프로세스 스케줄링 알고리즘의 SJF 방식과 비슷했다.

SJF 스케줄링이란, 최소작업 우선 스케줄링으로, 각 작업의 프로세서 실행 시간을 이용하여

프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업에 할당하는 방법이다.

해당 문제는 SJF 방식으로, 돈을 인출하는데 걸리는 시간(서비스시간)만 주어지고,

도착 시간은 모두 0으로 되어있는 사람들(프로세스들)의 대기시간의 합을 구하는 문제로도 볼 수 있다.

 

하지만 SJF 스케줄링을 모두 구현하기에는 시간이 오래걸릴것같아,

그리디 알고리즘을 통해 비교적 간단하게 구현했다.

 

해당 문제에서는 각 사람들이 돈을 인출하는데 필요한 시간의 합의 최소값을 구하는 것이 목표이다.

사람들이 돈을 인출하는데 필요한 시간의 합(person[i]의 합)이 최소가 되려면,

각 사람들이 돈을 인출하는게 필요한 시간(person[i])도 최소가 되어야한다.

 

그렇다면, 각 사람들이 돈을 인출하는데 걸리는 시간이 최소가 되게 하려면 어떻게 줄을 서야할까?

 

돈을 인출하는데 필요한 시간

= (각 사람이 기다린 시간) + (인출하는데 걸리는 시간)

 

이다. 인출하는데 걸리는 시간은 모두 정해져있으므로, 기다린 시간이 짧아지면된다.

기다린 시간이 짧아지려면, 인출하는데 걸리는 시간이 짧은 사람부터 먼저 인출을 하면 된다.

 

즉, 각 사람들이 돈을 인출하는데 필요한 시간의 합의 최소값을 구하려면,

돈을 인출하는데 걸리는 시간이 짧은 사람부터 줄을 서면 된다.

그리고, 해당 경우의 각 사람이 돈을 인출하는데 까지 걸린 시간의 합을 구하면 된다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int N; // 사람의 수 
	int person[1000];	// 돈을 인출하는데 걸리는 시간
	int waiting[1000];	// 각 사람이 돈을 인출하기까지 필요한 시간
    				// = (각 사람이 기다린 시간) + (인출하는데 걸리는 시간)
	int sum = 0;	// 각 사람이 돈을 인출하는데 필요한 시간의 합
			// = waiting 의 합

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> person[i];
	}

	// 돈 인출시간이 짧은 사람부터 정렬
	sort(person, person + N);
	
	// 기다린 시간의 초깃값 설정
	waiting[0] = person[0];

	// 각 사람이 돈을 인출하기까지 필요한 시간
	// = (각 사람이 기다린 시간) + (인출하는데 걸리는 시간)
	for (int i = 1; i < N; i++) {
		waiting[i] = person[i] + waiting[i - 1];
	}

	// 각 사람이 돈을 인출하는데 필요한 시간의 합(최소)
	//  = waiting 의 합
	for (int i = 0; i < N; i++) {
		sum += waiting[i];
	}

	cout << sum;

	return 0;
}

사람의 수(N)와 각 사람이 돈을 인출하는데 걸리는 시간(person[i])를 입력받아

돈 인출시간이 짧은 사람부터 정렬한다.

 

각 사람이 돈을 인출하기까지의 시간(waiting[i])은

(각 사람이 기다린 시간) + (인출하는데 걸리는 시간)이므로,

해당 값을 구한 뒤 waiting 배열에 넣어준다.

 

이후 waiting 값을 차례로 모두 더해주면,

각 사람들이 돈을 인출하는데 필요한 시간의 합의 최소값이 나오게 된다.

 

 

---

그리디 알고리즘 위주로 푸니까 뭔가 감이 조금 잡히는 것 같기도 하고..🤔

실버 3문제였는데 오히려 실버 4문제들보다 쉬웠던 느낌의 문제였다.