[C++] 그리디 알고리즘 예시 코딩

문제
작업의 수 N(1~100,000), 제한시간 D(1~10,000,000)
작업을 다수의 컴퓨터로 수행할 시 작업을 최소의 컴퓨터로 수행하는 컴퓨터의 수를 구하시오.

예시
1
10 14
7 5 4 6 1 2 3 5 2 3

computer1 : 7 3 2
computer2 : 5 1 2 5
computer3 : 4 6 3

#include <iostream>
#include <vector>// 작업목록을 담을 work 벡터
#include <queue>// 가까운 시간대를 찾기위한 우선순위 큐
#include <cstring>// 배열 초기화 memset사용

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); 
	cout.tie(); cin.tie();
	
	int TC, N, D, input;
	int computer[100001];

	cin >> TC;
	for (int t = 1; t <= TC; t++) {
		priority_queue<int>pq;//가까운 시간대로 time을 이동
		vector<int>work;
		memset(computer, 0, sizeof(computer));
		int slot = 1, min, total = 0;
        //slot : 작동시킬 컴퓨터 대수, min 다음 이동할 time, total : 총 작업량을 제한시간으로 나눈 몫 이상의 slot 갯수가 최소 필요
		cin >> N >> D;
		for (int i = 0; i < N; i++) {
			cin >> input;
			work.push_back(input);
			total += input;
		}
		slot = total / D;
		bool check = false, end = false;
		int w = 0;
		for (int time = 0; time <= D; time++) {
			for (int i = 0; i < slot; i++) {
				if (computer[i] - time == 0) {
					computer[i] += work[w];
					if (computer[i] > D) {
						check = true;
						cout << '\n';
						break;
					}
					else if(i != slot-1) {
						pq.push(-computer[i]);// 작은 것 먼저 꺼내기 위해 음수화
						cout << slot << ' ' << i << ' ' << computer[i] << ' ' << w << ' ' << work[w] << ' ' << time << '\n';
						w++;
						time--;
					}
					else {
						pq.push(-computer[i]);
						cout << slot << ' ' << i << ' ' << computer[i] << ' ' << w << ' ' << work[w] << ' ' << time << '\n';
						w++;
						min = -pq.top();
						pq.pop();
						time = min - 1;
					}
					if (w == N) {
						end = true;
					}
				}
			}
			
			if (check == true) {
				slot++;
				time = -1;
				w = 0;
				check = false;
				memset(computer, 0, sizeof(computer));
			}
			if (end == true) {
				break;
			}
		}
		cout <<'#'<<t<<' '<< slot << '\n';
	}

	return 0;
}

생각나는 예제를 구현해 보았는데 시간부분을 더 효율적으로 구현할 수 있는 방법을 생각해봐야겠습니다...

 

출처: https://tinyurl.com/y36kknwt