[C++] BOJ(백준) 7983 내일 할거야

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

7983번: 내일 할거야

 

그리디 문제다.

 

과제를 최대한 미뤄 내일부터 연속으로 최대 며칠 놀 수 있는지 구하는 문제다.

최대한 뒤로 미뤄야하기 때문에 맨 뒤에서부터 채워나갔다.

 

우선 마감일을 기준으로 정렬을 했다.

내림차순으로 데이터가 필요하지만 오름차순으로 정렬하고 뒤에서부터 접근했다.

마지막 마감일을 기준으로 걸리는 일수를 빼주고

그 후로는 이전 과제 시작일과 해당 과제 마감일 중 작은 값을 해당 과제의 마감일로 계산했다.

 

최종적으로 마감일이 가장 빠른 과제의 시작일 전까지 놀 수 있다.

 

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

int n, visit;
pair<int, int> arr[1000000];

int main() {
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;	cin >> a >> b;
		arr[i] = { b, a };
	}

	sort(arr, arr + n);

	visit = arr[n - 1].first - arr[n - 1].second;
	for (int i = n - 2; i >= 0; i--) {
		visit = min(visit, arr[i].first);
		visit -= arr[i].second;
	}

	cout << visit;
}