[JAVA]백준 2094번: 강수량

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

2094번: 강수량

1. 문제 설명

 

X 년도에는 Y 년도 이후 가장 많은 비가 내렸다 라고 말하려면 3가지 조건이 만족해야 한다.

 

1. Y 년도, X 년도, 그리고 그 사이의 모든 년도들의 강수량에 대한 정보가 알려져 있다.

2. X년도의 강수량은 Y 년도의 강수량 이하이다.

3. Y < Z < X를 만족하는 모든 Z에 대해서, Z 년도의 강수량은 X 년도보다 작다.

 

Y, X 두 정수가 주어질 때 세 가지 조건을 만족할 경우 true, 불가능할 경우에는 false, 강수량에 대한 정보가 알려져 있지 않은 년도에 대해서 강수량을 잘 가정할 경우 위의 세 조건이 만족할 때는 maybe를 출력한다.

 

2. 풀이

 

세그먼트 트리와 dp, 이분 탐색을 사용하였다.

 

Y, X 두 정수가 주어질 때 경우의 수는 크게 4가지로 나눌 수 있다.

 

1. Y, X 두 년도의 강수량을 모두 모르는 경우
2. Y 년도의 강수량만 아는 경우
3. X 년도의 강수량만 아는 경우
4. Y, X 두 년도의 강수량을 모두 아는 경우

 

먼저 1번, 두 년도의 강수량을 모두 모르는 경우의 경우 무조건 maybe이다.

 

Y, X의 강수량을 우리가 가정할 수 있기에 조건을 만족할 수 있도록 Y, X 년도의 강수량을 우리가 가정할 수 있기 때문이다.

 

 

2번, 3번, 4번의 경우를 위해 먼저 이분 탐색을 통해 Y, X 각각 연도 이상이 처음으로 나오는 인덱스 위치를 찾아야 한다.

찾은 인덱스의 년도 값과 X, Y가 같다면 4번의 경우, X만 같다면 3번의 경우, Y만 같다면 2번의 경우이다.

 

인덱스를 찾았다면 4번의 경우 조건 2를 만족하는지 확인해봐야 한다. 2번, 3번 경우는 확인할 필요가 없는데 1번과 같은 경우이다 (우리가 가정할 수 있기 때문)

 

그다음 세그먼트 쿼리를 수행하면 된다.

 

세그먼트 쿼리를 진행할 때 아까 이분 탐색으로 찾은 Y 인덱스와 X 인덱스 사이의 연도들의 최댓값을 구한 뒤 X와 비교해서 큰지 작은지 (조건 3) 확인하면 된다.

 

경우 2의 경우 Y+1 인덱스, X-1 인덱스 경우에 대해 쿼리를 진행하면 된다. 

 

X 년도가 X-1 인덱스, X인덱스 사이에 위치하기에 Z의 범위에 X-1인 덱스까지 포함되기 때문.

 

쿼리 진행 후, Z 년도들의 max값을 Y인덱스의 강수량과 비교하면 된다.

 

Y<Z<X년도에 대해서 강수량 Z < 강수량 X <= 강수량 Y를 만족해야 하지만, 현재 X 년도의 강수량을 모르는 상황이므로 강수량 Z < 강수량 Y를 만족하는지 대신 확인해야 한다.

 

경우 3의 경우 Y인덱스, X-1인덱스 경우에 대해 쿼리를 진행하면 된다.

 

Y 년도가 Y인덱스보다 작기 때문에 Y인덱스가 Z의 범위에 포함된다.

 

쿼리 진행 후, Z 년도들의 max값을 X인덱스의 강수량과 비교하면 된다.

 

경우 4의 경우  Y+1 인덱스, X-1 인덱스 경우에 대해서 쿼리를 진행하면 된다.

 

쿼리 진행 후, Z년도들의 max값을 X인덱스의 강수량과 비교하면 된다.

 

쿼리의 결과가 조건을 만족하지 못한다면 false를 출력하면 된다.

 

경우 2, 경우 3의 경우는 우리가 가정해서 주어지지 않은 가상의 연도를 만든 것이므로 조건을 만족하면 maybe를 출력한다.

 

그렇다면 경우 4의 경우는 조건을 만족하면 true일까..?

 

아니다..!!!!! (이것 때문에 틀렸다..)

 

조건 1을 보면 모든 년도의 강수량 정보가 있다고 적혀있다.

 

따라서 Y, X연도가 주어졌더라고 하더라도 그 중간에 연도가 연속적이지 않으면 maybe, 연속적이면 true를 출력해야 한다.

 

연속적인지를 알기 위해 dp를 사용. Y인덱스와 X인덱스의 차와 dp의 값이 같으면 true, 아니면 연속적이지 않은 것으로 판단 maybe를 출력한다.

 

 

*로직

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {

    // 정수 N
    public static int N;

    // 세그먼트 트리
    public static int[] tree;

    // 강수량들만 저장
    public static int[] rainy;

    // 년도 들만 저장
    public static int[] yearSave;

    // 년도 들이 이어지는지 확인
    public static int[] series;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        int question;

        tree = new int[N * 4];
        rainy = new int[N + 1];
        yearSave = new int[N + 1];
        series = new int[N + 1];


        for (int x = 0; x < N; x++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int year, rain;

            year = Integer.parseInt(st.nextToken());
            rain = Integer.parseInt(st.nextToken());

            rainy[x + 1] = rain;
            yearSave[x + 1] = year;


            // 이전 년도와 이어진다면 이어지는 길이 +1
            if (x > 0 && yearSave[x]+1 == year) {
                series[x + 1] = series[x] + 1;
            } else {
                series[x + 1] = 1;
            }

            update(1, N, rain, 1, x + 1);
        }

        question = Integer.parseInt(br.readLine());

        for (int x = 0; x < question; x++) {

            // Y X
            // X년도의 강수량은 Y년도 강수량 이하이다.

            int Yyear, Xyear;
            boolean result = false;

            StringTokenizer st = new StringTokenizer(br.readLine());

            Yyear = Integer.parseInt(st.nextToken());

            Xyear = Integer.parseInt(st.nextToken());

            int xIdx = startFind(Xyear);
            int yIdx = startFind(Yyear);

            boolean samexIdx = true;
            boolean sameyIdx = true;

            // 범위를 벗어나거나 xIdx의 년도 값이 xYear이 아닌 경우 -> 우리는 주어진 X year의 강수량을 모른다.
            if (xIdx < 0 || xIdx > N || yearSave[xIdx] != Xyear) {
                samexIdx = false;
            }

            // 범위를 벗어나거나 yIdx의 년도 값이 yYear이 아닌 경우 -> 우리는 주어진 Y year의 강수량을 모른다.
            if (yIdx < 0 || yIdx > N || yearSave[yIdx] != Yyear) {
                sameyIdx = false;
            }


            // 두 년도 다 모르면 -> maybe (가정하면 된다.)
            if (!samexIdx && !sameyIdx) {
                bw.write("maybe\n");
            } else {
                if (samexIdx && sameyIdx) {
                    result=isTrue(yIdx, xIdx, 0);

                } else if (samexIdx) {
                    result=isTrue(yIdx - 1, xIdx, 1);
                } else {
                    result=isTrue(yIdx, xIdx, 2);
                }

                // 조건 불만족 -> false
                if (!result) {
                    bw.write("false\n");
                    // 조건 만족, 두 년도 모두 알고 연속적이다. -> true
                } else if (samexIdx && sameyIdx && series[xIdx]-series[yIdx]==xIdx-yIdx) {
                    bw.write("true\n");
                } else {
                    // 조건은 만족하나... ->maybe
                    bw.write("maybe\n");
                }


            }
        }

        bw.flush();
    }

    public static boolean isTrue(int yIdx, int xIdx,int flag) {



        // 경우 4의 경우 조건 2 확인
        if (flag==0 && rainy[yIdx] < rainy[xIdx]) {
            return false;
        } else {
            xIdx--;
            yIdx++;

            if (yIdx > xIdx) {
                return true;
            } else {
                int midMax = query(1, N, yIdx, xIdx, 1);


                if (flag == 2) {
                    return midMax < rainy[yIdx - 1];
                }

                return midMax < rainy[xIdx + 1];
            }

        }

    }


    // x값 이상인 첫번째 인덱스 찾기.
    public static int startFind(int x) {
        int start = 1;
        int end = N + 1;

        while (start < end) {
            int mid = (start + end) / 2;

            if (yearSave[mid] < x) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return end;
    }

    // 세그먼트 트리 쿼리
    public static int query(int left, int right, int start, int end,int node) {
        if(right<start || end<left)
            return 0;

        if (start <= left && right <= end) {
            return tree[node];
        }

        int mid = (left + right) / 2;

        return Math.max(query(left, mid, start, end, node * 2), query(mid + 1, right, start, end, node * 2 + 1));
    }

    // 세그먼트 트리 업데이트
    public static void update(int left,int right,int rain,int node,int index) {
        if (left == right) {
            tree[node] = rain;
            return;
        }

        int mid = (left + right) / 2;

        if(index<=mid)
            update(left, mid, rain, node * 2, index);
        else
            update(mid + 1, right, rain, node * 2 + 1, index);

        tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
    }


}

 

많이 틀렸다