(백준) 넴모넴모 2020 _ 19845

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

 

🐢 설명

넴모넴모들이 왼쪽아래에 모여있다는 조건이 있으므로 쉽게 풀 수 있다.

 

우리가 구해야할 값은 레이저의 설치 좌표가 주어졌을 때 오른쪽에서 지울수 있는 넴모의 개수와 자신의 위 행에서 지울 수 있는 넴모의 개수의 합을 구하기만 하면 된다.

 

오른쪽에서 지울 수 있는 넴모 개수 구하기

이때 오른쪽은 비교적 쉽게 구할 수 있는데 각 층마다 알려준 넴모의 개수가 있으므로 이를 이용해서 계산하면 된다.

(y, x) 레이저 설치 시 지울 오른쪽 넴모의 개수 = 층에 존재하는 넴모 개수 - x (레이저 열 위치) + 1 (자기위치) 를 통해 구할 수 있다.

floorInfo[row - 1] - col + 1

만약 음수라면 0으로 치환해주는걸 잊지말자.

 

위에서 지울 수 있는 넴모 개수 구하기

위 행의 높이는 0~25만 사이의 값을 준다고 하였으므로 층이 25만개가 있다고 생각하자. 이때 각 층마다 가로 길이가 다르지만 중요한 점은 이미 정렬이 되어있다는 것이 핵심이다. 중력에 의해 위층은 아래층의 넴모 개수보다 작거나 같다고 하였으므로 이를 이용하면 된다.

 

따라서, 이분탐색을 통해서 주어진 좌표의 열값을 가지고 25만층의 넴모 개수들에 대해 이분탐색을 하면 된다. x의 값보다 큰 값을 갖는 마지막 층의 다음 위치를 구하면 된다. (= x값보다 작은 최초의 층)

3 3 2 0 0 ... 에서 col(x)보다 작은 맨 처음 위치 (여기선 3이다)

 

🐢코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 넴모넴모2020_19845 {
    static int N, Q;
    static int[] floorInfo;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder answer = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        Q = Integer.parseInt(st.nextToken());

        floorInfo = new int[250001];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            floorInfo[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < Q; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int countR = removeRight(y, x);
            int countU = removeUp(y, x);
            answer.append((countR + countU)).append("\n");
        }
        System.out.print(answer);
    }

    private static int removeUp(int y, int x) {
        int left = 0;
        int right = 250001;
        int mid;

        while (left < right) {
            mid = (left + right) / 2;

            if (floorInfo[mid] < x) {
                right = mid; // 왼쪽 탐색 (자기보다 작은 최초의 값 위치 찾기)
            }
            else {
                left = mid + 1; // 오른쪽 탐색
            }
        }
        int tmp = right - y;
        if (tmp < 0) tmp = 0;
        return tmp;
    }

    private static int removeRight(int y, int x) {
        int c = floorInfo[y - 1] - x + 1;
        if (c < 0) c = 0;
        return c;
    }
}

🐢 마무리