C++ 백준 13904번: 과제

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

13904번: 과제

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

---

풀이

하루에 과제를 하나할 수 있고 과제마다 마감일이 정해져있는데 , 점수가 최댓값이 되려면 마감일을 줄여가면서 그에 따른 점수들을 저장한다. 그리고 저장한 값들 사이에서 마감일이 줄어들 때마다 최댓값을 더해주고 그 최댓값은 삭제하면 된다.

 

1. 마감일과 점수를 pair로 저장한다

2. 마감일을 기준으로 내림차순 정렬한 후에 pivot 변수에 제일 큰 마감일 수 저장

3. for문으로 마감일 수가 같은 것들의 점수들은 v2라는 벡터에 저장한다. & for문 돌릴 때마다 pivot(마감일 수) 하나씩 빼준다.

4. v2벡터를 내림차순으로 정렬하고 제일 큰 값을 sum변수에 저장한 후 최종 답 도출

 

처음에 점수를 내림차순으로 정렬해서 구현했는데 마감일 수를 도통 어떻게 처리할 지 몰라서 바꿔서 마감일을 기준으로 내림차순 정렬했다.  for문 괄호 안에 조건 확인하는 부분을 마감일 제일 큰 수를 하지 않고 벡터 사이즈로 해서 고생을 좀 했지만 질문 게시판에서 반례 찾아서 겨우 해결

 

끔찍했다^^,,,

---

#include <bits/stdc++.h>
using namespace std;
vector <pair<int, int>> v1;

int main() {
	int count; cin >> count;
	while (count--) {
		int num1, num2;
		cin >> num1 >> num2;
		v1.push_back(make_pair(num1, num2));
	}
	sort(v1.rbegin(), v1.rend());
	vector<int> v2;
	int pivot = v1[0].first; // 제일 큰 마감일 수 
	int sum = 0;
	int cnt = 0;

	for (int i = 0; i < v1[0].first; i++) {
		for (int j = cnt; j < v1.size(); j++) {
			if (pivot == v1[j].first) { // 만약에 마감일 수 같은 거 있으면 저장
				v2.push_back(v1[j].second);
				cnt++;
			}
			else {
				break;
			}
		}
		pivot--; // 마감일 수 하나씩 줄여가면서 진행

		if (v2.size() != 0) {
			sort(v2.rbegin(), v2.rend());
			sum += v2[0]; //제일 큰 값 저장
			v2.erase(v2.begin());
		}
		if (pivot <= 0) { //종료조건
			cout << sum << endl;
			return 0;
		}
	}
	cout << sum << endl;
	return 0;
}