[백준] 과제 13904번 C++ 풀이

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

13904번: 과제

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
int arr[1001];
vector<pair<int, int>> v;
int N;
bool cmp(pair<int,int> a, pair<int,int> b)
{
	if (a.second > b.second)
		return true;
	return false;
}

int main(void)
{
	cin >> N;
	memset(arr, 0, sizeof(arr));
	for (int i = 0; i < N; i++)
	{
		int d, w;
		cin >> d >> w;
		v.push_back(make_pair(d, w));
	}
	sort(v.begin(), v.end(),cmp);
	for (int i = 0; i < N; i++)
	{
		for (int j = v[i].first; j > 0; j--)
		{
			if (arr[j] == 0)
			{
				arr[j] = v[i].second;
				break;
			}
		}
	}

	int res = 0;
	for (int i = 1; i <= 1000; i++)
		res += arr[i];
	cout << res;
}

 

최대 점수를 얻으려면

최대 점수를 주는 문제를 우선적으로 해야 합니다.

하지만 점수 많이 주는 과제를 바로 과제를 하는 것이 아닌 최대한 미룰 수 있을 때까지 미루다 과제를 해야 합니다.

 

예로 d=4, w=60인 과제가 있다고 생각해봅시다.

4일이 마감이기에 4일부터 과제를 시작할 수 있습니다.

하지만 4일에 못한다면 3일에 해도 2일에 해도 1일에 해도 그만입니다.

그렇기에 d는 4부터 1일까지 가능한 날짜에 과제를 하면 됩니다.

과제를 하는데 하루만 걸리기 때문입니다.

0일까지 내려간다면 이 과제는 할 수 없는 과제입니다.

 

이 방법으로 높은 점수를 주는 과제부터 우선적으로 과제 시작일을 계획하면 됩니다.

 

sort(v.begin(), v.end(),cmp);
	for (int i = 0; i < N; i++)
	{
		for (int j = v[i].first; j > 0; j--)
		{
			if (arr[j] == 0)
			{
				arr[j] = v[i].second;
				break;
			}
		}
	}

위의 코드는 정렬을 점수 기준으로 내림차순으로 합니다.

맨 첫 v는 최대 점수를 주는 과제가 있겠지요

끝으로 갈수록 점수가 작아집니다.

이것을 0번째 과제부터 N-1번째 과제까지 계획을 합니다.

 

for (int j = v[i].first; j > 0; j--)
{
	if (arr[j] == 0)
	{
		arr[j] = v[i].second;
		break;
	}
}

arr[j]는 j일에 과제를 하면 얻을 수 있는 점수가 들어갑니다.

v[i]번째 담긴 first는 과제의 dead line 입니다.

dead line부터 1일까지 과제가 시작 가능한 날짜인지 확인합니다.

arr[j]가 0이 아니라면 이미 과제를 계획한 날이라 점수가 들어가 있겠지요.

arr[j]가 0이라면 그날 과제 계획이 없는 것으로 그날 과제를 하면 되니깐

arr[j]를 v[i].second로 점수를 넣어줍니다.

 

int res = 0;
for (int i = 1; i <= 1000; i++)
	res += arr[i];
cout << res;

1일부터 1000일까지 얻은 과제의 점수들을 더해 출력합니다.