BOJ_7983

😭 문제가 나의 상황과 알맞다. 정말 아무것도 하기싫다. 하지만 해야한다.

• 내일부터 연속으로 최대 놀수있는 날을 구해야한다.
• 그러므로 중간중간 노는 날은 무시하고 처음 일을 시작하기 전까지만 구해주면 된다.
• 이말은 즉슨 맨 끝부터 차근차근 일을 하면서 맨 앞까지 오면 된다.
• 입력이 정렬이 되어있지 않으므로 정렬해줘야한다.
• 마감 기한이 가장 큰 것부터 정렬하고 그리디를 사용해서 풀어주면 될 것으로 보인다.

💻 그리디

    sort(v.begin(), v.end(), compare);

    int stand = v[0].second - v[0].first;
    for (int i = 1; i < N; i++)
    {
        if(v[i].second < stand)
        {
            stand = v[i].second - v[i].first;
        }
        else{
            stand = stand - v[i].first;
        }
    }

• 일이 끝난 날이 stand, 이 변수를 기준으로
  • 다음 마감기한 날짜가 더 작으면 마감기한에서 걸리는 시간을 마이너스
    : 마감기한까지 끝내줘야 하기 때문에 stand에서 걸리는 시간을 빼면 안된다.
  • 다음 마감기한 날짜가 더 크거나 같으면? 그냥 stand에서 빼준다.

💻 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string.h>

using namespace std;

#define endl "\n"

vector<pair<int,int> > v;

bool compare(pair<int,int> a, pair<int,int> b)
{

    return a.second > b.second;
}

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

    int N;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int day, finish;
        cin >> day >> finish;
        v.push_back(make_pair(day, finish));
    }

    sort(v.begin(), v.end(), compare);

    int stand = v[0].second - v[0].first;
    for (int i = 1; i < N; i++)
    {
        if(v[i].second < stand)
        {
            stand = v[i].second - v[i].first;
        }
        else{
            stand = stand - v[i].first;
        }
    }
    cout << stand << endl;
}