백준 23843 콘센트 c++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> vec;
vector<int> consent;
int n,m;

bool cmp(int a,int b) {
	return a > b;
}

void input() {
	cin >> n >> m;
	int tmp;
	for(int i=0; i<n; i++) {
		cin >> tmp;
		vec.push_back(tmp);
	}
}
	
void solve() {
	sort(vec.begin(),vec.end(),cmp);
	int time = 0; 
	for(int i=0; i<m; i++) {
		consent.push_back(vec[0]);
		vec.erase(vec.begin());
		if(vec.empty()) {
			break;
		}
	}
	
	while(1) {
		if(vec.size() == 0) {
			if(consent.empty()) {
				break;
			}
			sort(consent.begin(),consent.end(),cmp);
			time = time + consent[0];
			break;
		}
		sort(consent.begin(),consent.end(),cmp);
		time += consent[m-1];
		for(int i=0; i<consent.size(); i++) {
			consent[i] = consent[i] - consent[consent.size()-1];
		}
		
		for(int i=consent.size()-1; i>=0; i--) {
			if(consent[i] == 0) {
				consent[i] = consent[i] + vec[0];
				vec.erase(vec.begin());
			}
			if(vec.empty()) {
				break;
			}
		}
	}
	
	cout << time;
}

int main() {
	input();
	solve();
}

**  그리디 + 정렬  ** 

 

1. 충전 시간 기준 내림차순으로 전자기기를 정렬한다.

2. 정렬한 전자기기를 큰 순서대로 콘센트에 꽂는다.

2. 콘센트에 꽂힌 전자기기 중 가장 짧은 충전 시간을 가진 전자기기를 기준으로 콘센트에 꽂혀있는 전자기기의 충전시간을 빼준다.

3. 빼준 충전시간을 전체 시간에 더해준다.

4. 콘센트에 더 꽂을 전자기기가 없을 경우 남아있는 콘센트 중 가장 시간이 많이 남은 전자기기를 전체 시간에 더해준다.