[백준OJ] 13904번 과제

www.acmicpc.net/problem/13904

13904번: 과제

---

 

풀이)

먼저, 입력받은 마감날짜중 제일 마지막 날짜를 구해준다.

그런뒤 , 마지막 날짜부터 시작하여 1일차까지 반복문을 돌며, 입력받은 d,w쌍중, 끝내지 못한과제이면서, 마감날짜가 현재 돌고있는 반복문의 날짜보다 크거나 같은 쌍중 w의 최대값을 구해준다. ( 5일차일때 할수있는 과제중 최댓값을 구해야 하는데 4일차껄 풀어봤자 마감기한이 지났으므로 해당x이다.)

 그런뒤 최댓값을 찾아서 sum에 저장을 해주고, 해당 과제를 수행했다고 check를 해주며 1일차 까지 돌면된다.

 

시간복잡도)

d의 최댓값이 1000이고, N의 최댓값이 1000이므로  O(d*N) 이 된다. 충분히 시간안에 돌아간다.

 

코드)

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int n;
vector<pair<int, int>> v; //{d,w}
bool visited[1000];//수행했는지에 대한 bool 배열

int main() {
	cin >> n;
	int maxD = -1;
	for (int i = 0; i < n; i++) {
		int d, w;
		cin >> d >> w;
		maxD = max(maxD, d);//제일 늦은 제출기한을 구함
		v.push_back({ d,w });
	}
	int sum = 0;
	
    //마지막날부터 1일차로 접근
	for (int i = maxD; i >= 1; i--) {
		int tempMax = -1;
		int tempInd = -1;
        
    	//입력받은 배열을 돌며 수행을 하지않았고, 마감날짜가 아직 안지난 과제들에대해
        //최댓값 갱신
		for (int j = n - 1; j >= 0; j--) {
        	
			if (!visited[j] && v[j].first >= i&&v[j].second>tempMax) {
				tempInd = j;
				tempMax = v[j].second;
			}
		}
        //조건에 해당하는 순서쌍이 있으면
        //더해준 뒤, 수행했다고 체크
		if (tempMax != -1) {
			sum += tempMax;
			visited[tempInd] = true;
		}
	}

	cout << sum << "\n";
}