BOJ 17420 깊콘이 넘쳐흘러 해설

작성일 | In

문제 링크

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

해설

시간복잡도

$N$의 범위가 작기 때문에 $O(N)$의 시간복잡도로 문제를 풀 것이다.

문제 풀이

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

다른 말로, $B_i$가 가장 작을 때의 $i$는 $A_i$도 가장 작다.
또, $B_i$가 가장 큰 값일 때의 $i$는 $B_i$도 가장 크다.
이러한 성질 때문에, $B$를 오름차순 정렬했을때 대응되는 위치의 $A_i$ 값도 오름차순 정렬이 되어 있어야 한다.

하지만, $A_i$의 크기가 $B_i$의 크기보다 커야 정우가 원하는 일자에 기프티콘을 사용할 수 있기 때문에 $A_i$ ≥ $B_i$ 이 성립한다.

최종적으로 정리하자면, $B$를 오름차순 정렬하고 각 위치에 대응하는 곳에 $A_i$ 값들을 배치하면 아래의 두 식이 성립한다.
$A_i$ ≥ $B_i$
$A_{i - 1}$ ≤ $A_i$

반례

만약 $B_{i - 1}$과 $B_i$ 값이 같다면 굳이 $A_{i - 1}$ ≤ $A_i$ 식이 성립할 필요가 없다.
그렇기 때문에, $B_i$ 보다 작은 값을 가지고 있는 최댓값을 $B$에서 찾은 후, 두 $A$ 값들을 비교해주면 된다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(void) {
    ios::sync_with_stdio(0);
    ll n;
    cin >> n;
    vector<pair<ll, ll>> arr(n);
    for (ll i = 0; i < n; i++) {
        cin >> arr[i].second;
    }
    for (ll i = 0; i < n; i++) {
        cin >> arr[i].first;
    }
    sort(arr.begin(), arr.end());
    ll bef = ((max((ll)0, arr[0].first - arr[0].second + 29)) / 30) * 30 + arr[0].second;
    ll cnt = (max((ll)0, arr[0].first - arr[0].second + 29)) / 30;
    ll cache = 0;
    for (ll i = 1; i < n; i++) {
        ll tmp = (max((ll)0, max(bef, arr[i].first) - arr[i].second + 29)) / 30;
        cnt += tmp;
        if (i != n - 1 && arr[i + 1].first == arr[i].first) {
            cache = max(cache, tmp * 30 + arr[i].second);
            continue;
        }
        bef = tmp * 30 + arr[i].second;
        bef = max(bef, cache);
    }
    cout << cnt;
}