백준 23843번 콘센트 (C++)

https://www.acmicpc.net/problem/23843

23843번: 콘센트

 

- 접근법 -

 

먼저 콘센트의 개수가 최대 10개이기 때문에 시간복잡도에 큰 영향을 받지 않는 문제이다.

중요한 것은 콘센트들에 기기가 충전중 일 때 가장 오래걸리는 것을 꽂아놔야한다는 것이다. 만약 작은것 부터 꽂았다면 예제 1 1  4 4 8 에서

 

콘센트 1 - 1 4

콘센트 2  - 1 4 

 

이런식으로 꽂히게 될 것이고 이후 8이 들어오면 답이 아니다. 그러므로 먼저 큰 놈이 들어와서 자리를 잡아야한다. 그렇다면 

 

콘센트 1 - 8 , 1

콘센트 2 - 4 , 4, 1 

 

이런식으로 들어오게 될 것이다. 논리를 새워보면 콘센트는 가장 시간이 오래 걸리는 기기들 부터 충전을 하고, 콘센트에 다 꽂혀 있다면 가장 먼저 끝나는 콘센트에 다음 기기를 꽂을 것이고 시간은 더하여 저장할 것이다.

 

1. 먼저 내림차순으로 정렬한다.

2. 콘센트 중 가장 남은시간이 짧은 곳을 선택한다. 이 때 충전 시간은 더하여 갱신한다.

3. 반복

 

중요한것은 두번째의 가장 짧은 곳을 선택해야하는 것이다. 난 이렇게 구현을 했다.

 

	priority_queue<int> pq[10];

	for (int i = 0; i < M; i++) {
		pq[i].push(0);
	}

 

M개의 우선순위 큐를 모두 생성하고

 

for (int i = 0; i < N; i++) {
		int idx = 0;
		int min_value = 1231321313;
		for (int j = 0; j < M; j++) {
			if (pq[j].top() < min_value) {
				idx = j;
				min_value = pq[j].top();
			}
		}

		int tmp = pq[idx].top() + device[i];
		pq[idx].pop();
		pq[idx].push(tmp);
	}

 

이중 포문으로 내부 포문에서는 가장 남은 시간이 짧은 콘센트를 찾아내는 방식으로 구현했다. 이렇게 해도 시간복잡도는 O(N * M)으로 가능하다. 그러나 O(N)으로 풀어내는 방법이 있다. 내부 포문을 우선순위큐로 해결해버리고 각 콘센트를 우선순위 큐 안의 원소로 처리해버리는 방식이다.

 

priority_queue<int, vector<int>, greater<int>> pq;

for (int i = 0; i < M; i++)
		pq.push(0);

	sort(times, times + N, comp);

	for (int i = 0; i < N; i++) {
		int tmp = pq.top() + times[i];
		pq.pop();
		pq.push(tmp);
		priorq.push(tmp);
	}

 

이러면 내부에 처음 

0 0 의 원소가 있을 것이고

0 -> 8

최소힙 이므로 다음은 0이 나와서  0-> 4

최소힙 이므로 다음은 4 -> 8

최소힙 이므로 8 -> 9

그러므로 정답은 9

 

이렇게 내가 7달 전에 풀었다는데 그럴리가 없다 구글링충 ㅅㄲ. 우선순위 큐의 숫자가 워낙 작아서 이 문제에서는 시간차가 별로 없지만 아마 M이 커지면 상당히 차이가 날 것이다. 

 

코드 전체

// 내 풀이 O(N * M)

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

int main() {

	int N, M;
	cin >> N >> M;

	priority_queue<int> pq[10];
	vector<int> device;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		device.push_back(tmp);
	}

	sort(device.rbegin(), device.rend());

	for (int i = 0; i < M; i++) {
		pq[i].push(0);
	}

	for (int i = 0; i < N; i++) {
		int idx = 0;
		int min_value = 1231321313;
		for (int j = 0; j < M; j++) {
			if (pq[j].top() < min_value) {
				idx = j;
				min_value = pq[j].top();
			}
		}

		int tmp = pq[idx].top() + device[i];
		pq[idx].pop();
		pq[idx].push(tmp);
	}

	int answer = -1;

	for (int i = 0; i < M; i++) {
		answer = max(answer, pq[i].top());
	}

	cout << answer << '\n';
}

 

// 완벽 풀이 O(N)

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

priority_queue<int, vector<int>, greater<int>> pq;
priority_queue<int> priorq;

bool comp(long long a, long long b) {
	return (a > b);
}

int main() {
	int N, M;

	long long times[10001];

	cin >> N >> M;

	for (int i = 0; i < N; i++)
		cin >> times[i];

	for (int i = 0; i < M; i++)
		pq.push(0);

	sort(times, times + N, comp);

	for (int i = 0; i < N; i++) {
		int tmp = pq.top() + times[i];
		pq.pop();
		pq.push(tmp);
		priorq.push(tmp);
	}

	cout << priorq.top() << '\n';
}