백준: 17420. 깊콘이 넘쳐흘러 (C++)

1. 문제 정보

• https://www.acmicpc.net/problem/17420
• Platinum V
• 그리디

 

2. 문제 풀이

 

처음 문제 풀이 시 부터 풀이가 쉽게 보이는 편이라고 생각하고 막힘 없이 풀기 시작했었어요

하지만 그렇게 호락호락할 리가 없죠 🥲

제대로 처리하지 못한 코너 케이스들에서 막히게 되었어요 😭

그래서 ! 우리는 해당 케이스 분석으로 먼저 들어가보려 합니다

 

4
39 8 10 0
40 60 60 90

AC: 10
 

 

이 케이스를 먼저 확인해 볼 건데요

 

이 문제 풀이의 핵심은 정렬에 있습니다

문제의 조건을 보면 아래와 같습니다

 

• 기프티콘의 연장 횟수 최소화
• 기프티콘의 기한이 가장 짧은 것 먼저 사용
• 기프티콘의 사용 날짜는 정해져 있음
• 기프티콘은 하루에 동시에 여러 장 연장 또는 사용할 수 있음

이를 봤을 때, 기프티콘의 사용 날짜가 정해져 있으므로 이에 맞춰서 진행하는 것이 좋아보이네요

저는 사용 날짜에 따라 정렬하고, 날짜가 같다면 기한이 짧은 순으로 정렬했어요 😊

사실 날짜가 같은 경우를 따로 처리해줄 필요는 없긴 하지만, 편의상 이렇게 할게요 !

예시 케이스의 경우 이미 그렇게 정렬이 되어 있으므로 그대로 보시면 되겠습니다 😀

 

첫 기프티콘의 경우 40일에 사용할 예정인데 기한이 39일이에요

때문에 무조건 연장이 1회 필요합니다

 

그래서 1회 연장을 해주고, 그러면 배열은 이와 같아지겠죠?

이후에 60일에 기프티콘 2장을 사용해야 하는데, 기한이 짧은 것을 먼저 사용한다는 조건이 있어요

즉 60일에 맞춰 기프티콘을 사용하려면 앞서 40일, 기한 69일이 남은 기프티콘보다 기한이 길어야 한다는거죠

때문에 두 번째 기프티콘은 3회 연장을 해줘야합니다

 

그럼 배열은 이와 같이 될 것이죠
그 다음 세 번째 기프티콘도 연장을 해 줘야 하는데, 이 때 주의할 점이 있어요 👀

기준이 두 번째 기프티콘인 98이 아닌, 첫 번째 기프티콘인 69를 기준으로 해야 한다는 점이에요
사용 일자가 같기 때문에 이전에 사용한 기한보다만 높으면 되기 때문이지요 😊

 

 

이에 따라 세 번째는 69보다 크면서 연장 횟수를 최소화한 값인 70이 됩니다 !

그리고 마지막 기프티콘은 기한이 달라지죠?

그렇기에 이전 사용일(60일) 기준 가장 큰 값인 98보다 기한이 길어야 합니다

 

 

그래서 세 번 연장한 120이 기한이 되지요
이 과정을 거치면 총 연장이 1 + 3 + 2 + 4으로 10회 연장이 됩니다 🥰

 

이러한 방식으로 풀면 되고, 저는 이를 저장하기 위해 pre와 renew_max라는 변수를 사용했습니다

pre는 기준으로 삼을 이전 날짜 정보이고, renew_max는 pre를 바꿀 때 적용할 최대 값을 저장하는 변수에요 !

 

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

using namespace std;

#define ll long long

int n, x;
ll ans = 0;

int renew_max;
pair<int, int> pre;

vector<pair<int, int>> gifticon;

bool compare(pair<int, int> p1, pair<int, int> p2) {
    if (p1.second == p2.second) {
        return p1.first < p2.first;
    }
    else if (p1.second < p2.second) return true;
    else return false;
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x;

        gifticon.push_back({ x, -1 });
    }

    for (int i = 0; i < n; i++) {
        cin >> gifticon[i].second;
    }

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

    for (int i = 0; i < n; i++) {
        int prol1 = 0;
        int prol2 = 0;
        
        if (i == 0) {
            if (gifticon[0].first < gifticon[0].second) {
                prol1 = ceil((gifticon[0].second - gifticon[0].first) / 30.0);
            } 
            gifticon[0].first += prol1 * 30;
            pre = gifticon[0];
            renew_max = gifticon[0].first;

            ans += prol1;
        }
        else {
            if (gifticon[i].first < gifticon[i].second) {
                prol1 = ceil((gifticon[i].second - gifticon[i].first) / 30.0);
            }
            if (gifticon[i - 1].second != gifticon[i].second) {
                pre = { renew_max, gifticon[i - 1].second };
            }
            if (pre.first > gifticon[i].first) {
                prol2 = ceil((pre.first - gifticon[i].first) / 30.0);
            }

            gifticon[i].first += max(prol1, prol2) * 30;
            renew_max = max(renew_max, gifticon[i].first);

            ans += max(prol1, prol2);
        }
    }

    cout << ans;
}