[Beakjoon] 17420 깊콘이 넘쳐흘러 (C++)

문제 링크

BOJ 17420 : 깊콘이 넘쳐흘러

문제

정우는 생일을 맞아 친구들에게 기프티콘을 N개 선물받았다. 어떤 기프티콘을 언제 쓸지 다 계획을 정해놨는데, 멍청한 정우는 기프티콘에 기한이 있다는 사실을 까맣게 잊고 있었다. 다행히 기프티콘에는 기한 연장 기능이 있다. 한 기프티콘을 한 번 연장할 때마다 기한이 30일씩 늘어난다.

정우는 기프티콘의 기한 연장을 너무 귀찮아하기 때문에, 기한 연장을 최소한으로 하고 싶어한다. 그리고 정우는 강박증이 있어서, 남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다. 단, 기한이 가장 적게 남은 기프티콘이 여러 개라면 그 중 아무거나 선택할 수 있다. 하루에 여러 기프티콘을 사용하거나 연장하는 것 모두 가능하다.

최소 횟수로 기한 연장을 하면서 기프티콘을 다 쓸 수 있도록 정우를 도와주자.

입력

첫째 줄에 기프티콘의 수 N이 주어진다.

둘째 줄에 A1, A2, ..., AN가 주어진다. 이는 i번째 기프티콘의 남은 기한이 Ai일이라는 뜻이다.

셋째 줄에 B1, B2, ..., BN가 주어진다. 이는 i번째 기프티콘을 Bi일 뒤에 사용할 계획이라는 뜻이다.

출력

첫째 줄에 정우가 기한 연장을 해야 하는 최소 횟수를 출력한다.

정답이 32비트 정수를 넘을 수 있으므로 유의하라.

풀이

문제를 정확히 이해하는데 시간이 걸렸다.

• 기프티콘은 사용계획 날짜와 사용가능 기한이 정해져 있다.
• 기프티콘은 사용계획 날짜에 사용한다.
• 기프티콘을 사용할 때 기프티콘의 사용가능 기한은 가장 작아야 사용할 수 있다. (남아있는 기프티콘들의 각 사용가능 기한이 현재 사용할 기프티콘의 사용가능 기한보다 모두 더 커야한다.
• 한 번 연장시 30일 늘어난다.

즉 요약하자면 기프티콘을 정해진 날짜에 사용하되, 사용할 때 해당 기프티콘의 남은 기한이 최소가 되도록 한다.

같은 날짜에 여러개의 기프티콘을 사용할 수 있다.

사용날짜가 같은 경우에는 동시에 여러개를 사용할 수 있다.
즉 사용 날짜가 같을 때 그들 사이의 남은 날짜 최소값은 고려할 필요가 없다.

이 부분을 떠올리는 건 둘째 치고 구현하기가 까다로웠다.

예시

예시를 보면 문제를 이해하기 수월했다.
ex)

4
24 2 3 29
25 30 30 30

answer: 6

25일에 0번째 기프티콘을 사용한다.
이를 위해 0째를 1번, 1,2번째를 2번씩 업데이트 한다. (0번째 기프티콘을 사용하기 위해서 한 번 연장 ->54 여기서 54가 최소값이 돼야 하므로 1,2번째는 2번씩 업데이트 하여 각각 62,63)

30일에 3번째 기프티콘 1번 연장

총 6번의 연장이 필요하다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

#define endl "\n"
#define ll long long

using namespace std;

int N;
ll A[101010];
ll B[101010];
vector<pair<ll,ll>> V;

void Solve() {
    cin>>N;
    for(int i=0; i<N; i++) cin>>A[i];
    for(int i=0; i<N; i++) cin>>B[i];

    for(int i=0; i<N; i++){
        V.push_back({B[i],A[i]});
    }
    
    sort(V.begin(), V.end());
    
    ll answer=0, beforMaxDay=0;

    for(int i=0; i<V.size(); i++){
        
        ll maxDay = 0, resultDay, cnt;
        
        //사용 날짜가 같은 경우는 한 번에 처리한다.
        int idx = i;
        while(idx<V.size()){
            if(V[idx].first != V[i].first) {idx--; break;}  //사용날짜가 다른 경우 

            //기한이 사용 날짜보다 더 많이 남은 경우
            if(V[idx].second>=max(beforMaxDay, V[idx].first)) {
                maxDay = max(maxDay, V[idx].second);
                idx++;
                continue;
            }    

            cnt = ceil((max(beforMaxDay,V[idx].first)-V[idx].second)/30.0);
            answer+=cnt;
            resultDay = V[idx].second + cnt*30;
            maxDay = max(maxDay, resultDay);
            idx++;
        }
        //사용날짜가 같은 경우를 모두 확인 후 beforeMaxDay를 업이트
        i = idx;
        beforMaxDay = maxDay;
    }

    cout<<answer;
}


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

    return 0;
}