백준 17393 - 다이나믹 롤러(자바 - 이분탐색)

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

17393번: 다이나믹 롤러

 

* 문제 요약

페인팅 전문 회사 부키치 암즈는 거대한 페인팅용 롤러 "다이나믹 롤러" 를 출시하였다. 이 신제품은 평범한 페인팅 롤러와 마찬가지로 굴려서 칠할 수 있지만, 손잡이를 세로로 휘둘러 잉크를 한번에 흩뿌릴 수 있도록 설계되었다.

이러한 새로운 사용방법은 거대한 몸집과 맞물려 매우 역동적으로 보였기 때문에, 이 롤러의 이름은 다이나믹 롤러가 되었다.

평소, 페인팅에 관심이 많던 멩미는 다이나믹 롤러의 매력에 흠뻑 빠져 단숨에 다이나믹 롤러를 구매했다.

지금 당장 롤러를 시험해보고 싶었던 멩미는 통로 일부분을 칠해보기로 했다.

 

통로는 1 x N 길이의 일자 형태를 가지고 있고, 통로의 바닥은 1 x 1 타일로 가득 차있다. 각 타일은 잉크지수 Ai 와 점도지수 Bi 를 가지고 있다. 타일이 제각각 다른 특성을 가지고 있기 때문에 멩미는 세심하게 롤러를 휘둘러야만 한다. 멩미가 i번째 타일위에 서 있을 때, 멩미는 다이나믹 롤러로 현재 위치보다 오른쪽에 있으면서 점도지수가 서 있는 칸의 잉크지수 Ai 이하인 칸을 칠할 수 있다.

 

통로는 기본적인 관리가 되고 있기 때문에 각 칸의 잉크지수 Ai 는 점도지수 Bi 이상이다. 그러나 깊숙한 통로는 관리에 어려움이 있기 때문에 점도지수 Bi 는 항상 오름차순이다. 이런 상황속에서 멩미가 통로의 각 타일에서 서 있을 때 다이나믹 롤러로 칠할 수 있는 최대의 칸 수를 구해보자.

 

* 입력

첫 번째 줄에 통로의 길이인 자연수 N이 입력으로 주어진다. (1 <= N <= 5 x 10^5)

두 번째 줄에 N개의 정수 A1, A2, ... An 이 공백으로 주어진다. Ai 는 i번째 칸의 잉크지수를 의미한다.(1 <= Ai <= 10^18)

세 번째 줄에 N개의 정수 B1, B2, ... Bn 이 공백으로 구분되어 주어진다. Bi 는 i번째 칸의 점도지수를 의미한다. (1 <= Bi <= 10^18, Ai >= Bi)

B1, B2, ... Bn 은 오름차순이다. 즉, 1 <= i <= j <= N 을 만족하는 모든 정수 순서쌍 (i, j) 에 대해 Bi <= Bj 가 성립한다.

 

* 출력

첫 번째 줄에 N개의 정수 x1, x2, ... xn 을 공백으로 구분하여 출력한다. xi 는 i번째 칸에 서서 다이나믹 롤러를 사용할 때 최대로 칠할 수 있는 칸의 갯수이다.

 

* 예시

 

* 해결 과정

잉크지수와 점도지수 입력값을 각 배열에 저장해준 후 아래와 같이 이분탐색을 진행한다.

1. 반복문을 수행하되, start 에는 i+1 (i 는 현재 탐색중인 인덱스 위치에 해당되며, +1 을 해준 이유는 현재 서있는 타일의 오른쪽에 위치해 있는 타일들을 기준으로 이분탐색을 진행해야 하기 때문이다.), end 에는 점도지수 배열의 마지막 인덱스 값을 저장해준다.

2. index 변수에 (start + end) / 2 값을 저장해주고 난 다음 만약 점도지수 배열에서 index 위치에 있는 점도지수 값이 현재 탐색중인 잉크지수 배열의 값 보다 큰 경우, 현재 index 값으로 가리키고 있는 타일의 점도지수가 현재 서있는 타일의 잉크지수보다 크다는 뜻이므로 해당 타일은 다이나믹 롤러로 색칠해 줄 수 없다.

그러므로 점도지수가 더 낮은 타일을 찾기 위해 end 에 index - 1 값을 저장시켜서 index 에 더 작은 값이 저장될 수 있도록 범위를 줄여준다.

3. 만약 점도지수 배열에서 index 위치에 있는 점도지수 값이 현재 탐색중인 잉크지수 배열의 값 보다 작은 경우, index 위치에 해당되는 타일의 점도지수가 현재 서 있는 타일의 잉크지수 보다 낮다는 뜻이므로 다이나믹 롤러로 색칠이 가능하다.

그러므로 색칠이 가능한 타일 중 최대 점도지수를 가진 타일을 찾기 위해 start 에 index + 1 값을 저장시켜서 index 에 더 큰값이 저장될 수 있도록 범위를 줄여준다.

4. 이분탐색이 끝나고 나면 end - i 의 결과값을 결과 배열 resultArray 에 저장해준다. (end : 색칠할 수 있는 타일들 중 점도지수가 가장 높은 타일의 위치, i : 현재 위치이므로 두 값의 차이를 계산하면 자연스럽게 현재 서 있는 타일 위치를 기준으로 오른쪽에서 색칠할 수 있는 타일의 갯수를 구할 수 있다.)

5. 위의 방법으로 모든 타일에서의 색칠 가능한 타일 갯수를 구하고 나면 resultArray 배열의 각 값을 출력해주는 것으로 문제를 해결한다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int count = Integer.parseInt(br.readLine());
        long [] inkArray = new long[count];
        long [] visArray = new long[count];
        
        String[] input = br.readLine().split(" ");
        for(int i = 0; i < count; i++){
            inkArray[i] = Long.parseLong(input[i]);
        }

        input = br.readLine().split(" ");
        for(int i = 0; i < count; i++){
            visArray[i] = Long.parseLong(input[i]);
        }

        long[] resultArray = new long[count];
        for(int i = 0; i < inkArray.length - 1; i++){

            int start = i + 1;
            int end = visArray.length - 1;
            while(start <= end){
                int index = (start + end) / 2;

                if(visArray[index] > inkArray[i]){
                    end = index - 1;
                }
                else{
                    start = index + 1;
                }
            }

            resultArray[i] = end - i;
        }

        for(int i = 0; i < resultArray.length; i++){
            bw.write(resultArray[i] + " ");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

매 반복마다 현재 서 있는 타일에서 바로 오른쪽에 인접한 타일 위치를 start, 타일의 최대 길이를 end 로 하여 이분탐색을 수행하면서 색칠할 수 있는 타일 중 점도지수가 가장 높은 타일의 위치를 구함으로서 최종적으로 각 타일별로 오른쪽에 있는 타일 들 중 색칠할 수 있는 타일의 갯수를 하나하나 모두 구해줄 수 있었으므로 이분탐색 문제에 해당된다.