[BOJ 18866 // C++] 젊은 날의 생이여

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18866번 문제인 젊은 날의 생이여이다.
문제는 아래 링크를 확인하자.

https://www.acmcipc.net/problem/18866

 

첫 번째 날부터 \(k\)번째 날까지의 행복도의 최솟값이 \(k+1\)번째 날부터 \(N\)번째 날까지의 행복도의 최댓값보다 크고, 첫 번째 날부터 \(k\)번째 날까지의 피로도의 최댓값이 \(k+1\)번째 날부터 \(N\)번째 날까지의 피로도의 최솟값보다 작은 \(k\)의 값 중 가장 큰 값을 구하는 문제이다.

 

\(k\) 이하의 날의 행복도의 최솟값 및 피로도의 최댓값은 prefix min/max를 이용해 \(O(N)\)에 계산가능함을 관찰하자. 이는 \(k\) 이상의 날의 행복도의 최댓값 및 피로도의 최솟값에도 똑같이 적용할 수 있다.

 

따라서 위와 같은 전처리 후 각 \(k\)에 대하여 \(k\)번째 날이 젊은 날과 늙은 날을 구분하는 기준이 될 수 있는지를 각각 \(O(1)\)에 판정해 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;
int H[1000002], F[1000002];
int LH[1000002], RH[1000002], LF[1000002], RF[1000002];
int ans = -1;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++) cin >> H[i] >> F[i];
    LH[0] = 1000000007;
    for (int i = 1; i <= N; i++) {
        if (!H[i]) LH[i] = LH[i - 1];
        else LH[i] = min(LH[i - 1], H[i]);
    }
    for (int i = N; i > 0; i--) {
        if (!H[i]) RH[i] = RH[i + 1];
        else RH[i] = max(RH[i + 1], H[i]);
    }
    for (int i = 1; i <= N; i++) {
        if (!F[i]) LF[i] = LF[i - 1];
        else LF[i] = max(LF[i - 1], F[i]);
    }
    RF[N + 1] = 1000000007;
    for (int i = N; i > 0; i--) {
        if (!F[i]) RF[i] = RF[i + 1];
        else RF[i] = min(RF[i + 1], F[i]);
    }
    for (int i = 1; i < N; i++) {
        if (LH[i] > RH[i + 1] && LF[i] < RF[i + 1]) ans = i;
    }

    cout << ans;
}