백준 7983 내일할거야 c++

문제

아 과제 하기 싫다. 아무 것도 안 하고 싶다. 더 적극적이고 격렬하게 아무 것도 안 하고 싶다.

있잖아. 내가 아까 책상에다가 n개의 과제 목록을 적어놨어. 각각의 과제 i는 di 일이 걸리고, 오늘로부터 ti 일 안에 끝내야 해. 그러니까 오늘이 0일이면, ti일이 끝나기 전에 제출이야. 과제는 한번 시작하면 쉬지 않고 계속해야 해. 안 그러면 머리 아파 지거든.

근데 있잖아. 내가 지금 너무, 너무 아무 것도 안 하고 싶어. 그래서 오늘은 아무 것도 안 할 거야. 더 중요한 게 뭔지 알아? 사실 나 내일도, 모레도, 아무 것도 안 하고 싶어. 한 며칠 동안은 계속 아무 것도 안하려고. 아. 과제가 있을 때 내가 내일부터 연속으로 최대 며칠동안 놀 수 있는지 궁금하다. 궁금하긴 한데, 난 아무 것도 안 하고 싶어.

좋은 생각이 났다. 너희가 이걸 대신 구해주면, 내가 너희의 맞은 문제 수를 하나 올려줄게.

입력

첫째 줄에는 과제의 개수인 정수 n (1 ≤ n ≤ 106)이 주어진다.

이후 n개의 줄에 각각의 과제를 나타내는 두 정수 di, ti (1 ≤ di, ti ≤ 109)가 순서대로 주어진다. 오늘은 0일이다.

모든 입력에 대해, 오늘 아무 것도 안 해도 과제를 마무리 할 수 있는 방법이 존재함이 보장된다.

출력

내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다.

예제 입력 1 복사

3
2 8
1 13
3 10

예제 출력 1 복사

5

 

 

문제유형 - 그리디 알고리즘

 

1. vector <pair<int,int>>를 생성해준다

2. 입력을 받은후에 comp와 sort를 이용해서 벡터를 정렬 해 준다. pair vector의 두번째 값 이용해서 정렬하기 -> bool comp를 만들어주고 입력 인자를 pair<int,int> a , pair<int,int> b를 받아 준 후에 return a.second > b.second 하면 큰값 순서로 정렬이된다.

3. 정렬된 값을 이용하여 현재위치를 나타내는 맨 처음 now값을 설정해 준다 . 예 ) 13 - 1을 하면 12가 되는데 이 12값은 다음 과제의 기한이 시작 될 수 있는 지점을 말한다

4. for문을 n만큼 돌린다

5. int a , b 를 각 각 a에는 v[i].first 즉 과제 수행기간을 넣어주고 b에는 v[i].second 즉 과제 제출기한을 넣어준다

6. 만약에 now 보다 다음 과제 제출기한이 작거나 같다면 now = b-a를 해 준다 즉 과제 제출기한에서 과제 수행기간을 빼 주면 또 다음 현재 지점을 알 수 있다.

7. 만약에 now 보다 다음 과제 제출기한이 크다면 now = now - a를 해 준다 왜냐하면 now 보다 과제 제출 기한이 크더라도 어차피 now에 과제를 제출을 해야 하기 때문에 now에서 -a를 해 준다 .

8. 그럼 최종적으로 가장 연속으로 쉴 수 있는 값이 now에 저장되어 있게 된다 .

9. for루프를 빠져 나와서 now를 출력해 준다.

 

#include <bits/stdc++.h>

using namespace std;

int n;

vector<pair<int,int>>v;

bool comp(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);

    cin >> n;

    for (int i = 0; i <n ; ++i) {
        int a,b;
        cin >> a >> b;
        v.push_back({a,b});
    }

    std::sort(v.begin(), v.end(),comp);

    int now = v[0].second - v[0].first;

    for (int i = 1; i <n ; ++i) {
        int a = v[i].first;
        int b= v[i].second;
        if(now>=b){
            now = b-a;
        }else if(now<b){
            now = now - a;
        }
    }

    cout << now <<"\n";

}