https://www.acmicpc.net/problem/2094
레벨: P3
알고리즘 분류 : 자료 구조, 세그먼트 트리, 많은 조건 분기, 트리를 사용한 집합과 맵, 오프라인 쿼리,
값 / 좌표 압축, 희소 배열
[1] 문제 요약
N(1 ≤ N ≤ 50,000)개의 강수량 정보가 주어진다.이 정보는 연도 y(0 ≤ |y| ≤ 1,000,000,000)와 강수량 r(1 ≤ r ≤ 1,000,000,000)의 정수 쌍으로 주어지고, 연도에 따라 오름차순으로 주어진다.
이후 M(1 ≤ M ≤ 10,000)개의 쿼리가 주어진다. 하나의 쿼리는 두 개의 정수 Y, X (-1,000,000,000 ≤ Y < X ≤ 1,000,000,000)로 이루어져 있고, 이것은 “X년도에는 Y년도 이후 가장 많은 비가 내렸다.”라는 주장을 의미한다.
각 쿼리에 대해 출력될 내용에는 "true", "maybe", "false"가 있는데, 다음의 세 조건이 모두 만족되는 경우에는 "true", 조건을 만족시키는 것이 가능할 경우에는 "maybe", 그렇지 않을 경우에는 "false"를 출력하면 된다.
- 1) Y년도, X년도, 그리고 그 사이의 모든 년도들의 강수량에 대한 정보가 알려져 있다.
- 2) X년도의 강수량은 Y년도의 강수량 이하이다.
- 3) Y < Z < X를 만족하는 모든 Z들에 대해서, Z년도의 강수량은 X년도보다 적다.
[2] 문제 풀이
[2-1] "TRUE"
우선 어떤 경우에 쿼리의 답이 "true"가 될 수 있는지를 다시 살펴보자.
1) Y년도, X년도, 그리고 그 사이의 모든 년도들의 강수량에 대한 정보가 알려져 있다.
첫 번째 조건을 만족하기 위해서는 연도 X, Y와 그 사이의 모든 연도가 알려져 있는지를 확인하면 된다.
강수량 정보가 연도에 따라 오름차순으로 주어진다는 것을 알고 있으므로, X년, Y년이 있는지를 확인하기 위해서는 이분 탐색을 진행하면 된다. 입력된 순서대로 연도를 집어 넣은 배열을 year라고 이름 짓자. 강수량 정보는 오름차순으로 주어지므로 year 배열 또한 이미 오름차순으로 정렬되어 있다.
int xLBIdx = lower_bound(year, year + n, X) - year;
int yLBIdx = lower_bound(year, year + n, Y) - year;
if (year[yLBIdx] == Y) yExists = true;
if (year[xLBIdx] == X) xExists = true;lower_bound는 정렬된 배열에 대해, 어떠한 값보다 크거나 같은 가장 작은 값을 찾는다. 따라서 만약 X나 Y의 정보가 주어져 있다면, lower_bound는 X, Y의 인덱스 x, y를 찾게 될것이고, 이 경우 rain[yLBIdx] == rain[y] == Y, rain[xLBIdx] == rain[x] == X가 될 것이다.
그렇다면 Y년과 X년 사이의 강수량 정보가 모두 있는지를 확인하려면 어떻게 해야 할까? year 배열이 이미 오름차순으로 정렬되어 있으므로, 우리가 확인해야할 것은 x - y와 X - Y가 서로 일치하는가 하는 것 뿐이다. 만약 Y년도에서 X년도까지의 정보가 모두 알려져 있다면, x - y == X - Y가 될 것이고, 만약 그 사이에 누락된 연도가 있다면 x - y < X - Y가 될 것이기 때문이다.
2) X년도의 강수량은 Y년도의 강수량 이하이다.
마찬가지로 입력된 순서대로 강수량을 집어 넣은 배열 rain에 대해, rain[x] <= rain[y]인지만을 확인하면 된다.
3) Y < Z < X를 만족하는 모든 Z들에 대해서, Z년도의 강수량은 X년도보다 적다.
마지막으로는 Y 초과 X 미만의 구간의 최댓값이 Y의 rain[x]보다 작은지를 확인해야한다. 이 구간의 최댓값을 확인하기 위해서는 구간의 최댓값을 담은 세그먼트 트리를 활용하면 된다.
[2-2] "FALSE"
쿼리의 답이 "false"가 되는 경우는 조건 2, 3이 확실히 거짓이 되는 경우 뿐이다.
[2-3] "MAYBE"
쿼리의 답이 "maybe"가 될 때는 위의 두 번째, 세 번째 조건은 만족되지만 첫 번째 조건은 만족되지 않는 경우 밖에 없다. 즉 연도 X의 정보가 주어지지 않는 경우, Y의 정보가 주어지지 않는 경우, 혹은 그 사이의 연도가 주어지지 않는 경우 밖에 없다.
이 경우들은 다음과 같이 나눠볼 수 있겠다.
- X연도는 알지만 Y연도는 모를 때
- X연도는 모르지만 Y연도는 알 때
- 둘 다 모를 때
1) X연도는 알지만 Y연도는 모를 때
이 경우 우리는 Y < Z < X의 연도 Z들의 최댓값이 X연도의 강수량보다 작은지를 확인해야 한다.
이분탐색을 통해 얻은 인덱스 yLBIdx는 Y 이상의 가장 작은 연도를 가리키고, xLBIdx 또한 X 이상의 가장 작은 연도를 가리킨다. 그런데 Y연도의 정보를 가지고 있지 않기 때문에 y != yLBIdx이므로,yLBIdx는 (우리가 알고 있는) Y를 초과하는 최소 연도의 인덱스이고, X연도의 정보는 가지고 있으므로 xLBIdx == x이다. 따라서 우리가 확인해야 할 것은 구간 [yLBIdx, x - 1]의 최댓값이다.
만약 이 구간의 최댓값이 X연도의 강수량보다 작다면 이 경우는 가능한 경우라고 할 수 있겠다.
2) X연도는 모르지만 Y연도는 알 때
이 경우 우리는 Y < Z < X의 연도 Z들의 최댓값이 Y연도의 강수량보다 작거나 같은지를 확인해야 한다.
쿼리의 답이 "true"가 되기 위해서는 연도 Z들의 강수량이 X연도의 강수량보다 작아야 하고, X연도의 강수량은 Y연도의 강수량보다 작거나 같아야 하기 때문이다.
따라서 우리가 확인해야 할 것은 구간 [yLBIdx + 1, x - 1]의 최댓값이다.
3) 둘 다 모를 때
두 연도의 강수량 정보를 모두 가지고 있지 않은 경우에는 항상 "maybe"이다.
[3] CODE
#include <iostream>
#include <algorithm>
using namespace std;
#define NMAX 50000
int n, y, r, m, Y, X;
int year[NMAX], rain[NMAX];
int tree[NMAX * 4];
int max(int a, int b){
return a > b ? a : b;
}
int makeTree(int start, int end, int root){
if (start == end) {
tree[root] = rain[start];
return tree[root];
}
int mid = (start + end) / 2;
tree[root] = max(makeTree(start, mid, root * 2), makeTree(mid + 1, end, root * 2 + 1));
return tree[root];
}
int segSearch(int start, int end, int root, int left, int right){
if (right < start || end < left) return 0; //탐색할 수 없는 연도들의 강수량은 0이라고 생각하자
if (left <= start && end <= right) return tree[root];
int mid = (start + end) / 2;
return max(segSearch(start, mid, root * 2, left, right), segSearch(mid + 1, end, root * 2 + 1, left, right));
}//각 구간의 최댓값을 담은 세그먼트 트리.
int main(){
scanf("%d", &n);
for (int i = 0; i < n; i++){
scanf("%d%d", &y, &r);
year[i] = y; //연도를 입력받는 순서대로 넣은 배열
rain[i] = r; //강수량을 입력받은 순서대로 넣은 배열
}
makeTree(0, n-1, 1); //최댓값을 담은 세그먼트 트리를 만들어 주자
scanf("%d", &m);
for (int i = 0; i < m; i++){
scanf("%d%d", &Y, &X);
bool yExists = false;
bool xExists = false;
int xLBIdx = lower_bound(year, year + n, X) - year; //X 이상의 최소 연도 찾기
int yLBIdx = lower_bound(year, year + n, Y) - year; //Y 이상의 최소 연도 찾기
if (year[yLBIdx] == Y) yExists = true; // 만약 그것이 Y연도와 일치한다면 Y의 정보를 알고 있다는 것이고
if (year[xLBIdx] == X) xExists = true; // X에 대해서도 마찬가지이다.
if (yExists && xExists){ //X, Y연도의 정보를 모두 알고 있는 경우.
if (rain[xLBIdx] <= rain[yLBIdx]) {//조건 2
if (X - Y == 1) printf("true\n"); // 이 경우는 따로 생각함(후술)
else if (segSearch(0, n-1, 1, yLBIdx + 1, xLBIdx- 1) < rain[xLBIdx]) {//조건 3
if (X - Y == xLBIdx - yLBIdx) printf("true\n"); //조건 1
else printf("maybe\n");
}
else printf("false\n");
}
else printf("false\n");
}
else if (yExists){//y는 확실한데 x는 아닌 경우 : y의 다음 해 ~ x보다 작은 가장 큰 연도를 고려해야 함
if (X - Y == 1) printf("maybe\n");
else {
int maxRain = segSearch(0, n-1, 1, yLBIdx + 1, xLBIdx - 1);
if (rain[yLBIdx] > maxRain) printf("maybe\n"); //조건 2 & 3
else printf("false\n");
}
}
else if (xExists){//x는 있는데 y는 아닌 경우
if (X - Y == 1) printf("maybe\n");
else {
int maxRain = segSearch(0, n-1, 1, yLBIdx, xLBIdx - 1);
if (rain[xLBIdx] > maxRain) printf("maybe\n"); //조건 2 & 3
else printf("false\n");
}
}
else printf("maybe\n");
}
}[4] 주의점
1)
코드에서 각 경우들에 대해 X - Y == 1의 경우를 따로 분리해놓은 것은 우리가 최댓값을 탐색해야하는 구간이 [Y, X]가 아니라 [Y + 1, X - 1]이기 때문이다. 만약 X - Y == 1이 되면, 예컨대 Y = 2002, X = 2003이라면 세그먼트 트리로 탐색해야할 구간이 [2003, 2002]이 되어 제대로 탐색이 이루어지지 않는다.
2)
문제를 풀면서 아주 많이 헤맸는데, 그 이유는 질문 게시판의 글 때문이었다.
정보가 주어지지 않은 연도의 강수량의 최솟값도 1로 두어야 하지 않겠느냐는 글이었는데, 문제를 풀다 틀려서 이 글을 읽고 그에 맞게 구현했는데 도저히 맞을 수가 없었다. 알고보니 틀린 이유는 다른 데에 있었고, '혹시 정보가 주어지지 않은 연도의 강수량을 0으로 두면 통과할까?' 생각해서 바꿨더니 바로 통과할 수 있었다.
