문제 이해 단계
https://www.acmicpc.net/problem/18866
18866번: 젊은 날의 생이여
욱제의 젊은 날이 될 수 있는 최대 기간, 즉 문제의 조건을 만족할 수 있는 최대의 1 ≤ K < N을 출력한다. 단, 이러한 K가 없을 경우, -1을 출력한다.
www.acmicpc.net
N개의 (행복도, 피로도) 정보쌍이 들어온다.
그리고 1 ~ K ~ N이 실수로 주어진다.
그리고 그 사이에 실수 K가 주어지는데
K를 기점으로 K를 포함한 이전 값은 젊은 날, 그 이후에는 늙은 날로 구분된다.
그리고 젊은 날과, 늙은 날은 아래와 같은 두 가지 조건이 있다.
1. 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
2. 임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.
위 조건에서 (행복도, 피로도) 쌍은 i 년도씩 순서대로 들어온다.
0으로 들어오는 입력은 누락된 것이다.
해당 상황일 때 나올 수 있는 젊은 날, K의 최댓값을 구하는 문제
문제 접근 단계
제한사항부터 살펴보자.
N의 개수는 최대 1,000,000개.
그리고 행복도와 피로도의 최대는 10^9이다.
더하는 연산도 없기 때문에 딱히 int 자료형 이상을 써야 할 일도 없다.
그다음으로 딱 봐도 중요해 보이는 문제에서 주어진 조건을 해석해 보자.
1. 임의의 젊은 날의 행복도는 임의의 늙은 날의 행복도보다 높다.
2. 임의의 젊은 날의 피로도는 임의의 늙은 날의 피로도보다 낮다.
말을 복잡하게 써놨다.
1번의 말을 좀 더 쉽게 풀어보자면,
젊은 날에 포함된 그 어떤 행복도를 골라도
늙은 날에 있는 모든 행복도보다 높다는 것이다.
좀 더 직관적이게 수학적으로 표현해 보면,
젊은 날에 있는 행복도의 최솟값이,
늙은 날에 있는 행복도의 최댓값보다 크다.
그럼 2번 말도 비슷한 맥락으로 해석된다.
젊은 날에 있는 피로도의 최댓값이, 늙은 날에 있는 피로도의 최솟값보다 작다.
이 2가지 힌트를 가지고 문제를 풀면 된다.
문제를 해결하는 로직
우리가 구해야 하는 것은 젊은 날을 유지할 수 있는 최대 기간이다.
이 말은 위의 조건을 최대한 얼마만큼 유지할 수 있냐는 것이다.
한마디로, 저 조건이 깨지는 순간이 젊은 날을 유지할 수 있는 기간의 최대이다.
어떤 년도에서 젊은 날에 있는 피로도가 늙은 날에 있는 피로도보다 높아지거나,
젊은 날에 있는 행복도가 늙은 날에 있는 행복도보다 낮아지거나 하는 날 말이다.
우리는 그 순간을 찾으면 된다.
결국 필요한 것은 총 4가지이다.
젊은 날에 있는 행복도의 최솟값과 피로도의 최댓값
늙은 날에 있는 행복도의 최댓값과 피로도의 최댓값 연도를
계속 지나가면서 해당 4가지 정보를 계속 갱신한다.
그러다가 조건에 위배되는 순간이 끝나는 순간이다.
피로도 행복도 최대 최소 저장해 두기
그런데 이걸 매번 탐색할 때마다 그 위치에 따른 최댓값과 최솟값을 찾는 게 맞을까? 4가지 정보나 되는데?
N이 최대 1,000,000개다.
일일이 계산하면 O(n^2)인데 10^6 * 10^6을 하면 딱 봐도 시간초과다.
그래서 4가지 정보를 위치에 따라
늙은 날, 젊은 날에 따라 따로 저장해 두고 호출해서 사용했다.
그리고 사용할 때는 젊은 날 K와
늙은 날 K+1과 비교해서 맞는지를 확인한다.
이는 코드로 좀 더 자세히 확인하겠다.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int v[1000000][2]; // (행복도,피로도) 쌍
int main(){
cin.tie(0); cout.tie(0); cout.tie(0);
int N;
cin >> N;
for(int i = 0; i < N; i++){
int v1,v2;
cin >> v1 >> v2;
v[i][0]= v1;
v[i][1]= v2;
}
int young[N][2], old[N][2]; // 젊은날, 늙은날 최대 최소 정보
int max_happy = 0;
int min_happy = INT32_MAX;
int max_tired = 0;
int min_tired = INT32_MAX;
// 젊은 날은 1부터 ~ K까지
for(int i = 0; i < N; i++){
// 0이 들어오면 누락이기 때문에 예외처리 따로 해줌
if(min_happy > v[i][0] && v[i][0] != 0) min_happy = v[i][0];
if(max_tired < v[i][1] && v[i][1] != 0) max_tired = v[i][1];
young[i][0] = min_happy; // 행복도의 최솟값
young[i][1] = max_tired; // 피로도의 최댓값
}
// 늙은 날은 N-1부터 비교해야함(K-1 ~ N까지)
for(int i = N-1; i >= 0; i--){
// 0 누락 예외처리
if(max_happy < v[i][0] && v[i][0] != 0) max_happy = v[i][0];
if(min_tired > v[i][1] && v[i][1] != 0) min_tired = v[i][1];
old[i][0] = max_happy; // 행복도의 최댓값
old[i][1] = min_tired; // 피로도의 최솟값
}
int ans = 0;
for(int i = 0; i < N-1; i++){
// 조건에 부합하는 경우만 추출
if(young[i][0] > old[i+1][0] && young[i][1] < old[i+1][1]){
ans = i+1; // 인덱스니까 +1
}
}
if(ans == 0) ans = -1; // 인덱스가 여전히 0이면 경우가 없는 것
cout << ans;
}young 2차원 배열과, old 2차원 배열에 최댓값과 최솟값 정보를 저장하였다.
앞에 x축은 1 ~ N의 위치를 뜻하고
뒤에 y축([2])은 0은 행복도, 1은 피로도를 뜻한다.
입력으로 들어온 행복도와 피로도 쌍을 탐색하면서 최댓값과 최솟값을 찾는다.
젊은 날은 1 ~ K까지이기 때문에 순차 탐색하고
늙은 날은 K-1 ~ N이기 때문에 여기에 해당하는 최대 최소는 역순으로 탐색해야 한다.
둘 다 1 ~ N개를 탐색하는 것이기 때문에 O(N)의 시간 복잡도를 가진다.
배열 수집이 완료됐으면 판별에 들어가
조건에 부합하는 경우만 ans로 확정시켜 준다.
순차적으로 해줬기 때문에 마지막에 들어가는 것이
가장 최댓값(젊은 날의 최댓값)이 된다.
ns = 0인 경우에는 없는 것으로 간주하고 -1을 출력하도록 한다.
시행착오
요즘 골드 5도 잘 못 풀겠다. 슬럼프인가?
처음에는 그리디인 줄 알고 그리디로 접근했고, 정렬을 이용해서 풀었다.
어 이거 쉬운데?라고 구현했다가
틀렸습니다 폭탄맞고 처음부터 구현했다.
그다음에는 DP로 풀려고 했다가 도저히 각이 안 나와서 실패했다.
결국 1시간 30분이 지나서 답을 봤다.
답을 보니까 뭔가 당연한 생각이었다.
조건을 해석한 것은 나도 했는데, 왜 그다음 생각을 안 했는지 모르겠다.
정확히는 했긴 했는데 당연히 시간초과가 날 것이라고 생각하고 넘겼던 것 같다.
이래서 시간복잡도 계산하는 방법이 중요한 것 같다.
토스아이디
toss.me