[C++] 백준 17420: 깊콘이 넘쳐흘러

문제 이해

- 기프티콘이 N개 있으며 사용 가능 기한이 존재한다.

- 기한은 연장이 가능한데 한 번 연장하면 30일이 늘어난다.

- 기한 연장은 최소한으로 하려 한다.

- 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용 가능하다.

- 기한이 같은 게 여러 개면 아무거나 사용할 수 있다.

- 하루에 여러 개를 사용하거나 연장하는 것 모두 가능하다.

 

<조건>

- 시간 제한: 1초

- 메모리 제한: 512MB

 

<입력>

- N: 기프티콘의 수 (1 ~ 100,000, 10^5)

- Ai: 기프티콘의 남은 기한(1 ~ 1,000,000,000, 10^9)

- Bi: i번째 기프티콘의 경우 Bi일 뒤에 사용할 계획이다.(1 ~ 1,000,000,000, 10^9)

 

<출력>

- 기한 연장을 해야 하는 최소 횟수를 출력하라.

※ 32비트 정수를 넘을 수 있다.

 

 

문제 풀이

https://justicehui.github.io/sunrin-ps/2019/11/20/BOJ17420/

백준17420 깊콘이 넘쳐흘러

나정휘님의 코드를 참고하여 풀이를 진행하였다.

더 깔끔한 코드는 위의 포스트에 잘 나와있다!

 

 

 

문제의 풀이는 다음과 같이 진행된다.

1. 입력 받기

2. 구조체에 자료 넣기

3. 남은 기한이 계획보다 작을경우 연장해주기.

4. 사용 계획별로 오름차순 정렬

5. 계획대로 사용할 수 있도록 남은 기한 추가로 연장해주기

 

문제를 푸는 대부분 5번에서 어려움을 겪을 거 같아 그 부분은 자세히 서술해보려고 한다.

 

 

2번. 구조체에 자료 넣기

- 단순히 pair로 넣어도 되지만 first나 second를 사용하면 헷갈릴 위험이 높아 구조체를 따로 사용해주었다.

struct Gift{
    long long leftDays;
    long long plan;
};

vector<Gift> v;

...

v.push_back({leftDays[i], plan[i]});

 

 

3번. 남은 기한이 계획보다 작을경우 연장해주는 것은 당연하다.

- 계획 전에 기한이 종료되면 안 되기 때문이다.

 

※ 이때 주의할 점은 단순히 while문으로 반복할경우 시간제한 1초에 걸릴 수 있다는 것이다.

=> 그렇기에 몫을 구한 뒤에 30을 곱한 값을 더해주는 방식으로 진행한다.

※ 또한, 문제에서 32비트 자료형을 넘길 수 있다고 되어있으므로 long long형으로 받아야함도 잊지 말자.

if(v[i].leftDays < v[i].plan){
   long long tmp = (v[i].plan - v[i].leftDays + 30 - 1) / 30;
   v[i].leftDays += tmp * 30;
   ans += tmp;
}

 

 

 

4번. 사용 계획별로 정렬하기

계획 순서대로 정렬해주는 것은 당연하다. 여기까지는 많은 사람이 잘 해냈을 것이다.

bool cmp(Gift &a, Gift &b){
    if(a.plan == b.plan){
        return a.leftDays < b.leftDays;
    }
    return a.plan < b.plan;
}

...

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

 

 

5번. 계획대로 사용할 수 있도록 남은 기한 추가로 연장해주기

문제의 지문에 굵게 강조되어 있는

남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다.

는 문구로 인해 필요되는 작업이다.

 

4
24 2 3 29
25 30 30 30
6

필자는 질문 칸에 있는 위의 테스트 케이스를 통해 파악하였다.

 

 

여기서 핵심은 사용 계획 일자가 같은 기프티콘들이다.

 

사용 계획 일자가 작은 것보다는 사용 기한이 커야하며,

사용 계획 일자가 큰 것보다는 사용 기한이 작아야 한다.

 

이를 위해 pivot을 하나 두고 next라는 변수를 통해 사용 계획이 같은 날짜들끼리 구간으로 묶어 정렬한다.

 

 

코드는 다음과 같다.

주석에 설명을 해두었으니 이해가 가지 않으면 천천히 읽어보길 바란다.

long long pivot = 0;
    for(int i = 0; i < n; i++){ // 남은 기한끼리 순서 조정
        long long next = i + 1;
        while(next < n && v[next-1].plan == v[next].plan) next++;
        //next 변수로 사용 기한이 같은 기프티콘들 구분하기.

        for(int j = i; j < next; j++){
            if(pivot > v[j].leftDays){ //pivot보다 작은 값들 연장
                long long tmp = (pivot - v[j].leftDays + 29) / 30;
                v[j].leftDays += tmp * 30;
                ans += tmp;
            }
        }

        sort(v.begin()+i, v.begin()+next, cmp); //사용 기한이 같은(i ~ next-1 구간) 기프티콘끼리 정렬

        pivot = max(pivot, v[next-1].leftDays); //구간의 최댓값으로 pivot 갱신
        i = next - 1; //같은 구간을 정렬할 필요는 없으므로 i값 초기화
    }

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct Gift{
    long long leftDays;
    long long plan;
};

long long n, ans = 0;
long long leftDays[100005];
long long plan[100005];
vector<Gift> v;

bool cmp(Gift &a, Gift &b){
    if(a.plan == b.plan){
        return a.leftDays < b.leftDays;
    }
    return a.plan < b.plan;
}

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

    cin>>n;
    for(int i = 0; i < n; i++) cin >> leftDays[i];
    for(int i = 0; i < n; i++) cin >> plan[i];

    for(int i = 0; i < n; i++){ // 남은 기한 계획보다 늘려놓기.
        v.push_back({leftDays[i], plan[i]});
        if(v[i].leftDays < v[i].plan){
            long long tmp = (v[i].plan - v[i].leftDays + 30 - 1) / 30;
            v[i].leftDays += tmp * 30;
            ans += tmp;
        }
    }

    sort(v.begin(), v.end(), cmp);
        
    long long pivot = 0;
    for(int i = 0; i < n; i++){ // 남은 기한끼리 순서 조정
        long long next = i + 1;
        while(next < n && v[next-1].plan == v[next].plan) next++;
        //next 변수로 사용 기한이 같은 기프티콘들 구분하기.

        for(int j = i; j < next; j++){
            if(pivot > v[j].leftDays){ //pivot보다 작은 값들 연장
                long long tmp = (pivot - v[j].leftDays + 29) / 30;
                v[j].leftDays += tmp * 30;
                ans += tmp;
            }
        }

        sort(v.begin()+i, v.begin()+next, cmp); //사용 기한이 같은(i ~ next-1 구간) 기프티콘끼리 정렬

        pivot = max(pivot, v[next-1].leftDays); //구간의 최댓값으로 pivot 갱신
        i = next - 1; //같은 구간을 정렬할 필요는 없으므로 i값 초기화
    }

    cout<<ans;
    return 0;
}