[ALGORITHM] 백준 17420 - 깊콘이 넘쳐흘러

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

17420번: 깊콘이 넘쳐흘러

주의할 점

연장할 필요가 없는 경우가 어떤 조건 인지 생각해보자.

어떤 순간에 기프티콘 기한을 연장해야 하는지 생각해보자.

기한이 가장 적게 남은 기프티콘은 사용 가능한 기한이 아니라 사용까지 남은 기한을 의미한다고 생각하자.

 

예제

2
100 70
30 30

0

4
24 2 3 29
25 30 30 30

6

1
1
1
0

코드

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef struct dat{
    int A,B;
}d;

struct cmp{
    bool operator()(d &a, d &b){
        if(a.B == b.B)
            return a.A<b.A;
        return a.B<b.B;
    }
};

int N;

vector<d> C;

long long ans=0;
void input(){
    int num;

    cin>>N;

    C.resize(N);
    for(int i=0;i<N;i++)
        cin>>C[i].A;

    for(int i=0;i<N;i++)
        cin>>C[i].B;
}

void solution(){
    sort(C.begin(),C.end(),cmp());

    int pmax=C[0].B;
    int cmax=-1;
    for(int i=0;i<N;i++){
        int A=C[i].A;
        int B=C[i].B;
        if(pmax > A){
            int num=(pmax - A + 29)/30;
            ans += num;
            
            A += num*30;
        }
        

        cmax = max(cmax, A);
        if(i<N-1 && B != C[i+1].B){
            pmax = max(cmax,C[i+1].B);
        }
    }
    cout<<ans<<'\n';
}

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

    input();
    solution();

    return 0;
}