[BOJ/백준 13904/C++] 과제

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초

- 메모리 제한 : 256MB

 

[문제 풀이]

이런 문제처럼 작업을 스케쥴링 하는 문제들은 여러가지로 풀 수 있지만 필자는 처음에 두가지 방법으로 접근을 시도한다.

 

• 작업들을 끝냈을때 얻을 수 있는 코스트들이 높은 순서대로 정렬하고 시작.
• 가장 먼저 끝나는 기준으로 정렬 후 시작.

위 두 가지 방법으로 접근을 한다.

 

근데 여기서 2번째 방식으로 접근을 시도하면 문제가 풀리지 않는다.

 

당장 문제에서 주어진 예제를 살펴보자.

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

위 예제에서 먼저 끝나는 순서대로 선택하면(같은 경우 점수가 높은거) (1,20) → (2,50) → (3,30) → (4,60) → (6,5)를 선택하게 될텐데 이때 얻을 수 있는 점수는 165점이다. 근데 정답은 185점이니 사실상 이 방법으로는 못 푼다는 얘기다.

 

따라서 작업들을 점수가 높은 순서대로 정렬하고, 그 작업을 추가했을때 작업들을 올바르게 끝낼 수 있는지 확인하며 추가해준뒤 점수를 다 더해보았다.

 

bool cmp(pii& a, pii& b)
{
	return a.second > b.second;
}

///////////////////////////////////
......
///////////////////////////////////

for (int i = 0; i < N; i++)
{
    cin >> dt[i].first >> dt[i].second;
}

sort(dt.begin(), dt.end(), cmp);

pii는 pair<int,int>다.

 

점수들이 높은 순서대로 정렬을 먼저 한 뒤.

 

int ans = dt[0].second;
vector<int> ans_d;
ans_d.push_back(dt[0].first);
for (int i = 1; i < N; i++)
{
    vector<int> dummy = ans_d;

    dummy.push_back(dt[i].first);
    sort(dummy.begin(), dummy.end());

    bool flag = true;
    for (int j = 0; j < dummy.size(); j++)
    {
        if (dummy[j] >= j + 1) continue;
        else { flag = false; break; }
    }
    if (!flag) continue;
    else
    {
        ans_d.push_back(dt[i].first);
        ans += dt[i].second;
    }
}
cout << ans;

작업들을 하나씩 추가하고, 마감일만을 따로 배열에 저장 후 오름차순으로 정렬 한 뒤 인덱스의 순서와 작업의 마감기간중 인덱스 값이 더 큰 경우가 존재하면 그 작업조합은 수행할 수 없다는 것을 의미함으로 추가하지 않았다.

 

문제에서 주어진 예제를 통해 설명하면

4 60
2 50
4 40
3 30
1 20
4 10
6 5

정렬을 하면 위와 같이 되어있을 것이고, 순서대로 집어넣는다면 중간에 4,2,4,3까지는 선택되었을 것이다. 여기서 1을 추가하고 정렬을 하면 1,2,3,4,4가 되는데 여기서 마지막 4의 작업이 5일차때 수행할 수 있음으로 이 조합은 수행할 수 없는 조합이다. 그래서 최종적으로는 4,2,4,3,6 작업(정렬 전 : 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 작업)이 선택될 것이다.

 

[소스 코드1]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define pii pair<int,int>

using namespace std;

int N;
vector<pii> dt;

bool cmp(pii& a, pii& b)
{
	return a.second > b.second;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	dt.resize(N);
	for (int i = 0; i < N; i++)
	{
		cin >> dt[i].first >> dt[i].second;
	}

	sort(dt.begin(), dt.end(), cmp);

	int ans = dt[0].second;
	int day = 0;
	vector<int> ans_d;
	ans_d.push_back(dt[0].first);
	for (int i = 1; i < N; i++)
	{
		vector<int> dummy = ans_d;

		dummy.push_back(dt[i].first);
		sort(dummy.begin(), dummy.end());

		bool flag = true;
		for (int j = 0; j < dummy.size(); j++)
		{
			if (dummy[j] >= j + 1) continue;
			else { flag = false; break; }
		}
		if (!flag) continue;
		else
		{
			ans_d.push_back(dt[i].first);
			ans += dt[i].second;
		}
	}
	cout << ans;
}

 

음...

 

풀긴했는데 시간이 맘에 안든다.

 

추가적으로 한번 시간을 줄여보도록하자.

 

당연히 시간이 오래 걸리는 곳이 작업을 선택하는 부분일 것이다.

 

선택하는 방법을 아래와 같이 한번 바꿔보았다.

vector<bool> ans_d;
	int ans = 0;
	ans_d.resize(max_day+1);
	for (int i = 0; i < N; i++)
	{
		for (int j = dt[i].first; j >= 1; j--)
		{
			if (ans_d[j]) continue;
			else
			{
				ans += dt[i].second;
				ans_d[j] = true;
				break;
			}
		}
	}

1부터 가장 긴 마감일까지 배열을 만들고, 작업을 추가할건데 작업이 선택되면 마감일부터 1씩 줄여가면서 배열에 저장해준다.

 

간단하게 설명하자면, 문제에서 주어진 예제가 있고 정렬이 진행된 후에 (4,60)짜리 작업을 선택하고 4일차에 배치했다는 의미로 ans_d[4]를 true로 만들어준다.

 

 

다음 (2,50)짜리 작업을 선택하고 2일차에 배치했다는 의미로 ans_d[2]를 true로 만들어준다.

 

다음 (4,40)짜리 작업을 선택하고 4일차에 배치하려고 했는데 이미 앞에서 4일차에는 작업이 배치되어 있다. 여기서 하루씩 줄여나가면서 빈 날에 이 작업을 추가하면 3일차에 작업을 배치해준다. ans_d[3]를 true로 만들어준다.

 

다음 (3,30)짜리 작업을 선택하고 3일차에 배치하려고 했는데 이미 2일차,3일차에 작업이 있기 때문에 1일차에 작업을 배치한다. ans_d[1]를 true로 만들어준다.

 

다음(1,20)짜리 작업을 1일차에 배치하려고 했는데 1일차에는 이미 작업이 있고 가장 빠른날이기 때문에 이 작업은 배치가 불가능하기 때문에 넘어간다.

 

다음(6,5)짜리 작업은 6일차에 배치해준다. ans_d[6]를 true로 바꿔준다.

 

 

얻을 수 있는 점수들은 작업이 배치될때 , true로 바꿔주는 연산이 일어날때 ans변수에다가 계속 더해준 뒤 마지막에 출력하면 정답이 된다.

 

[소스 코드2]

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <list>
#include <math.h>
#include <map>
#include <queue>
#include <stack>

#define pii pair<int,int>

using namespace std;

int N, max_day = 0;
vector<pii> dt;

bool cmp(pii& a, pii& b)
{
	return a.second > b.second;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	dt.resize(N);
	for (int i = 0; i < N; i++)
	{
		cin >> dt[i].first >> dt[i].second;
		max_day = max(max_day, dt[i].first);
	}

	sort(dt.begin(), dt.end(), cmp);
	
	vector<bool> ans_d;
	int ans = 0;
	ans_d.resize(max_day+1);
	for (int i = 0; i < N; i++)
	{
		for (int j = dt[i].first; j >= 1; j--)
		{
			if (ans_d[j]) continue;
			else
			{
				ans += dt[i].second;
				ans_d[j] = true;
				break;
			}
		}
	}
	cout << ans;
}

 

굳