ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 11399 ATM (C++)

Posted on Feb 1, 2021 #그리디   #Algorithm  

11399 | ATM

🙋‍♀️ 문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

**중간 생략

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

🙌 입출력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

🙋‍♂️ 예제 입출력

5
3 1 4 3 2

32

🚀 코드

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

int main() {
	// 필요한 시간이 작은 순서대로 정렬되야 기다리는 시간이 최소

	int n = 0;
	list<int> li;
	int x = 0;
	int sum = 0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		li.push_back(x);
		sum += x; // 가장 마지막 사람이 기다리는 시간의 총 합
	}

	li.sort();
	int tmp = 0;
	int rst = 0;

	for (int i = 0; i < n; i++) {
		rst += sum; // 한 사람이 기다리는 시간의 총합을 더함
		sum -= li.back(); // 앞서 더한 사람의 필요 시간을 뺌
		li.pop_back();
	}
	cout << rst;
	return 0;
}

🌠 메모

먼저 필요한 시간이 적은 사람 순으로 리스트를 정렬한다. 이를 통해 필요한 시간의 총합을 최소로 만든다.

이후, 가장 오래 기다리는 사람부터 필요한 시간의 합을 구한다. rst += sum; 가장 오래 걸리는 사람은 자신을 포함하여 모든 사람의 필요한 시간의 합이고, 그 다음으로 오래걸리는 사람은, 방금 구한 가장 오래걸리는 사람의 필요 시간을 빼면 기다리는 시간을 구할 수 있다. sum -= li.back();

위를 반복하여 각 사람이 돈을 인출하는데 필요한 시간의 합을 구할 수 있다.



# 카테고리