[C++/알고리즘] 백준 13904 (과제)

 

www.acmicpc.net/problem/13904

13904번: 과제

 

 

우선 입력받은 데이터를 점수를 기반으로 정렬했다. 

vector의 second에 점수가 first에 과제 제출 기한이 담겨있다. 

 

탐욕법을 이용해서 푸는 문제로 점수를 기준으로 가장 큰 수부터 마감일에 가깝게 넣는다. 

오름차순으로 정렬된 벡터의 값에서 0번은 (한 번 돌릴 때마다 erase를 해주므로) 제일 점수가 큰 값이다.

따라서 0번을 뽑아서 해당 마감일에 이미 다른 점수가 있으면 전 날, 전전날을 계속 찾아본다.

비어있는 날이 있다면 해당 날짜에 넣고 없다면 버린다. 

 

 

왜 계속 틀렸을까 고민했던 문제이다. 그래서 이것저것 잘못 생각한 게 있었나 고민해봤지만 답이 나오지 않았다. 

그럴 수 밖에.. 틀린 이유는 따로 있었다.

밑에 answer에 더해주는 for문에서 n의 범위값을 틀려서 계속 채점 오류가 발생했다.

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool cmp(const pair<int, int> &a, const pair<int, int> &b) 
{
	if (a.second == b.second)
	{
		return a.first < b.first;
	}
	return a.second > b.second;
}

int max_score(vector<pair<int, int>>& v, int &n)
{
	vector<int> tempv;
	tempv.resize(1001);
	int idx = 0;
	int answer = 0;
	while (idx < n) {

		for (int i = v[0].first; i > 0; --i)
		{
			if (tempv[i] != 0)
			{
				continue;
			}
			else
			{
				tempv[i] = v[0].second;
				break;
			}
		}

		idx += 1;
		v.erase(v.begin());
	}

	for (int i = 0; i <=1000; ++i)
	{
		answer += tempv[i];
	}
	return answer;
}


int main()
{
	vector<pair<int, int>>  v;
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int n1, n2;
		cin >> n1 >> n2;
		v.push_back(make_pair(n1, n2));
	}
	sort(v.begin(), v.end(), cmp);
	int answer = max_score(v, n);
	cout << answer;
    
    return 0;
}