백준 11399. ATM

ATM

간단한 그리디 문제

1. 간단 설명

---

ATM이 한대밖에 없어서, 사람들이 줄을 서서 인출하는 상황

사람의 수와, 그 사람이 인출하는데 걸리는 시간이 주어진다

첫째 줄에 사람의 수 N이 주어지고

둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다.

각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력하는 문제

2. 예시

---

P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 이 주어졌다면

[1,2,3,4,5] 순서로 줄을 섰을 땐,

1번은 3분

2번은 3분 + 1분 = 4분

3번은 3 + 1 + 4 = 8분

4번 : 3 + 1 + 4 + 3 = 11

5번 : 11 + 2 = 13

12345로 섰을 때 전체 시간의 합은 3 + 4 + 8 + 11 + 13 = 39분이 된다

3. 알고리즘

---

최대 사람 수는 1000명이므로

각 경우의 수마다 직접 구하는건 1000! 돌려야 하므로 1초 내에 불가능하다

쇼핑대에서 계산할때 생각해보면, 가장 계산시간이 적은 사람한테 먼저 양보하는게 결과적으로 빨랐다

이를 이용해서 계산시간이 적은 사람을 앞에 배치하는 방법을 사용

3 1 4 3 2 를 오름차순으로 정렬하면 1 2 3 3 4

이 경우에는 1 + (1+2) + (1+2+3) + (1+2+3+3) + (1+2+3+3+4) = 32 이다

필요 변수

• int N
• int P[1001] 각 사람이 걸리는 시간
• int res 결과값 저장용

4. 소스코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int N;
int P[1001];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> P[i];
	}
	sort(P, P + N);

	int res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= i; j++) { // 누적합
			res += P[j];
		}
	}
	cout << res;

	return 0;
}

방법만 떠올리면 매우 간단한 그리디 문제였다