1. 문제 설명 📌

2. 접근 방식 🗃️

KEY WORD: 누적 합, 이분 탐색

동굴의 높이인 H와 깊이인 N이 각각 \(10^{5}\)이므로, 완전 탐색으로 하나의 행마다 모든 열을 조회한다면 1초에 \(10^{10}\)번 이상의 연산을 해야해서 시간 초과가 날 것이다.

해당 문제는 *거꾸로 매달려 있는 종유석을 어떻게 처리할 것인가?* 에 대한 명확한 가이드라인만 계획할 수 있다면 풀 수 있는 문제이다. 종유석 처리방법에 따라 두 가지 방법으로 풀 수 있는데, 하나는 누적 합이고 다른 하나는 이분 탐색이다.

(1) 누적합

a. 결론 먼저

1. "석순과 종유석 입력을 분류하여 Y축 위치에 따른 각 산물의 위치를 저장하는 배열 구현"
2. "각 배열의 누적합 구하기 (석순 누적합 배열을 sum_S[i], 종유석 누적합 배열을 sum_J[i]라고 한다.)"
3. "각 배열의 누적합은 개똥벌레가 돌파하는 위치가 i라고 쳤을 때,"
    " 누적합[i]는 그것이 만나는 장애물의 개수를 뜻하는 것이므로, sum_S[i] + sum_J[i]가 최소인 것과 나온 개수를 출력한다."

b. 해설

누적합으로 처리하기 위해서는 먼저 석순과 종유석의 배열을 정의하고 시작해야 한다. 석순, 종유석 배열을 각각 S[], J[]라고 할 때, Index는 주어진 높이 내의 Y축 좌표 (0~H), Value는 해당 Y 좌표를 끝 점으로 가지는 석순 혹은 종유석의 개수이다. 예를 들어 설명해보겠다. 입력이 다음과 같다고 하자.

분류해보면, 석순의 경우 각각 길이가 1,1,3,5이고, 종유석은 5,5,3,1이다.

하지만 여기서 종유석의 경우 거꾸로 매달려 있음으로, 5,5,3,1이 가르키는 끝점의 위치는 전체 길이에서 해당 숫자들을 뺀 3,3,5,7이 될 것이다. 이렇듯 종유석의 Y 좌표는 그것의 길이를 변환해서 도출해야 한다. 이를 배열로 나타낸다면 다음과 같을 것이다.

i	0	1	2	3	4	5	6	7
S[i]	0	2	0	1	0	1	0	0

i	0	1	2	3	4	5	6	7
J[i]	0	0	0	2	0	1	0	1

이제 이걸로 누적합을 구해보자.

누적합을 구하는 이유는?

만약 우리가 행이 높이, 열이 깊이인 2차원 배열로 문제를 풀었다면 어떻게 했을까? 개똥벌레가 H==1에서 출발한다 했을 때, i=1인 행을 모두 조회하며 만나는 석순 혹은 종유석의 개수를 일일히 세야 했을 것이다. 다음과 같이 말이다.

하지만 만약 첫 번째 열에 각 높이에서 출발했을 부딪히는 장애물의 개수를 미리 적어놓는다면 어떻게 될까?

우리는 첫 번째 열만 봐야하므로, 모든 열을 조회해야하는 수고를 덜 수 있을 것이다. 이것을 어떻게 할 수 있을까? 우리가 구한 배열에서 S[i]는 y좌표가 i인 지점을 끝점으로 가지는 석순의 개수였다. 이걸 뒤에서부터 누적시키면, 각 행에서 start 했을 때, 만나는 석순의 개수가 나온다. 그도 그럴 것이, S[5] = 1, S[3] = 1 인데, 높이가 1인 구간에서 출발했을 경우, 이보다 높은 끝점을 가지는 석순을 무조건 만나게 된다.

i	0	1	2	3	4	5	6	7
S[i]	0	2	0	1	0	1	0	0

i	0	1	2	3	4	5	6	7
누적	4	4	2	2	1	1	0	0

종유석의 경우 반대로 앞에서부터 누적해야한다. 왜냐하면, 거꾸로 매달려 있어서 우리가 J[ ]를 만들 때, 길이를 위치로 변환했기에, 위치 값이 작을수록 길이는 긴 것이기 때문이다. (ex - J[3]은 길이가 5인 종유석임)

i	0	1	2	3	4	5	6	7
J[i]	0	0	0	2	0	1	0	1

i	0	1	2	3	4	5	6	7
누적	0	0	0	2	2	3	3	4

이제 남은 것은 sumS[i] + sumJ[i]의 최소값과 그것의 개수만 구하면 된다. 각 배열이 높이가 i인 경우 부딪히는 석순 혹은 종유석의 개수이기 때문이다.

(2) 이분탐색

a.결론 부터

1. "석순과 종유석을 따로 받아 배열을 만든다. (i = 석순 혹은 종유석의 개수, v = 각 산물의 길이)";
2. "각 배열을 오름차순 정렬하고 이분 탐색을 시작한다.";
3. "0~H 중 하나를 target 값으로 설정하고, 이분탐색을 통해, target값보다 크거나 같은 산물의 개수를 구한다.";
4. "높이가 target값인 것보다 크거나 같다는 것은 H = target에서 출발했을 때 부딪힌다는 뜻이므로,";
    "그것의 최소값과 그 개수를 출력하면 된다."

b. 해설

이번에 구하는 석순과 종유석 배열은 직관적으로, i = 석순 혹은 종유석의 번호 (i가 각 배열 별로 N/2개가 존재해야함), v = 각 산물의 길이로 생각하면 된다. 이후 이분탐색을 위해 오름차순 정렬한다.

i	0	1	2	3
S[i]	1	1	3	5

i	0	1	2	3
J[i]	1	3	5	5

우리는 LowerBound를 사용할 것이다. LowerBound는 target 값과, 현재 mid가 가르키는 값이 같을 경우에도 하향조정하는 이분 탐색을 의미한다. 석순 배열에 대해서 먼저 해보면, target = 1일 경우, 이분탐색을 통한 S[mid]의 mid는 결국, 0을 가르키게 된다. 왜냐하면 이미 target값과 같은 S[1]을 만나더라도 하향조정되어 mid는 1에서 0으로 갈 것이기 때문이다. 이처럼 LowerBound를 사용하는 이유는 중복되는 최소값도 빠짐없이 계산에 포함시켜, target값에서 개똥벌레를 출발 시켰을 때, 부수는 장애물을 모두 세기 위해서이다.

종유석의 경우 계산이 좀 다르다. 석순 이분탐색에 넣은 target 값이 i라면 종유석에서는 H-i이 되어야 한다. 왜냐하면 종유석은 거꾸로 매달려있기 때문이다. 전체 높이가 7일 때, 석순입장에서 높이가 1인 지점은 종유석 입장에서 높이가 6인 지점이기 때문이다.

c. 석순 위치를 종유석 위치로 변환할 때, i ➜ H-i로 변환시키지 않고, i ➜ H-i+1로 변환시키는 이유

내가 가장 헷갈린 부분이다. 분명 위에서 살펴본 바와 같이, 석순에게 높이가 1인 지점은 종유석 입장에서는 높이가 6이다. 하지만 문제 해답을 보면 석순 입장에서 높이가 1인 지점을 종유석 입장에서 높이가 5인 지점으로 계산하고 있다. 이유는

접하는 지점은 개똥벌레가 충돌하는 장애물로 상정하지 않으므로, 계산에서 제외하기 위해서 이다.

문제에서는 예를 들어 높이 = 1인 지점에서 출발하지 않고, 0 ~ 1 사이 구간에서 출발한다고 한다. 따라서 우리가 편의상, int 값인 1 혹은 6, 7등으로 계산하는 것은 문제에서 바라는 N-1 ~ N 사이 구간에서 출발과 간극이 있다. 편한 int형으로 문제를 풀면서도, 이러한 둘 사이의 괴리를 없애기 위해서 종유석 계산 시 +1을 더한 것이다.

석순의 경우 왜 +1 안함?

우리는 어찌되었든 편의상 int형으로 계산해야한다. 따라서 접하는 지점은 생길 수 밖에 없다. 그렇다면 접하는 지점에 대한 정의를 다시 내려야한다. 이제부터 개똥벌레가 h = i인 지점에서 출발했을 때 장애물과 접한다는 사실 개똥벌레가 h = i보다 0.1 낮은 지점에서 출발해서 부딪힌다.로 수정한다. 그렇다면 밑과 같은 그림은

사실

임으로 석순에서는 따로 보정처리 안해줘도 된다. 문제가 되는 것은 종유석인데,

H=4에서 출발했다는 뜻은, 사실 3.9에서 출발했다는 뜻임으로, 위와 같이 3개를 접하지 않고,

2개를 접한다. 예시를 잘보면 3.9에서 만나는 녀석들은 h=3에서도 최소한 접하거나 만난다. 이를 활용해 종유석에서 계산 시 접하는 지점은 계산에서 제외하기 위해 +1 하는 것이다.

3. 코드 소개 🔎

(1) 누적합 풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        int N, H;
        int [] seok;
        int [] jong;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        seok = new int [H+1];
        jong = new int [H+1];

        for (int i = 0; i < N; i++) {
            if(i%2 == 0) seok[Integer.parseInt(br.readLine())]++;
            else jong[H - Integer.parseInt(br.readLine()) + 1]++;
        }

        for (int i = H-1; i >= 0; i--) {
            seok[i] +=seok[i+1];
        }

        for (int i = 1; i < H+1; i++) {
            jong[i] += jong[i-1];
        }

        int min = N;
        int cnt = 1;
        for (int i = 1; i < H+1; i++) {
            if(min > seok[i] + jong[i]){
                min = seok[i] + jong[i];
                cnt = 1;
            }else if (min == seok[i] + jong[i]){
                cnt++;
            }
        }
        System.out.printf("%d %d", min, cnt);
    }
}

(2) 이분탐색 풀이

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        int min = Integer.MAX_VALUE;
        int cnt = 0;
        int N, H;
        int [] seok;
        int [] jong;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        seok = new int [N/2];
        jong = new int [N/2];
        for (int i = 0; i < N; i++) {
            if(i%2 == 0) seok[i/2] = Integer.parseInt(br.readLine());
            else jong[i/2] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(seok);
        Arrays.sort(jong);


        for (int i = 1; i < H+1; i++) {
            int seok_crush = binary_search(i, seok);
            int jong_crush = binary_search(H-i+1, jong);
//            System.out.println(i+": "+seok_crush + " " + jong_crush);
            int total = seok_crush + jong_crush;
            if(min > total){
                min = total;
                cnt = 1;
            }else if(min == total) {
                cnt++;
            }

        }
        System.out.printf("%d %d", min, cnt);
    }
    public static int binary_search(int height, int [] arr){
        int ans = Integer.MAX_VALUE;
        int max = arr.length-1;
        int min = 0;
        while (min <= max){
            int mid = (max + min)/2;
            if(arr[mid] >= height){
                max = mid - 1;
                ans = Math.min(ans,mid);
            }else min = mid + 1;
        }
        return ans == Integer.MAX_VALUE? 0: arr.length - ans;
    }
}