(백준) 블록쌓기 _ 9998

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

 

🐢 설명

이분탐색으로 접근하면 되는데 이분탐색의 중요한 점은 1. 뭘 기준으로 할 것인지, 2. 정렬이 되어 있는지. 이 두가지가 중요한 부분이다.

참고로 1조는 2^40승 정도이고 각 높이에서 N개의 블럭을 비교하면서 이동 블럭의 개수를 세므로 시간복잡도는 N * log(높이)이 되고, N은 30만 정도이므로 대략 30만 * 40 = 1200만 번의 연산 으로 약 1초 내로 풀이가 가능하다.

 

고로 여기서는 V자형으로 지어야 하는 블럭에 대해 가장 낮은 높이를 갖는 가운데 부분의 높이를 기준으로 탐색을 하게 된다. 0 ~ 최대 가능 높이를 이분탐색하며 h일때 움직여야 하는 블럭의 개수를 확인해서 더 높이 지을지 낮게 지을지를 판단하면 된다. 참고로 최대 가능 높이는 1조(10^12)가 아니라 1조 - N/2 이다. 이유는 V자 형으로 지어야 하므로 한칸 당 높이가 1씩 낮아지므로 가로가 N이면 가운데의 최대 높이는 N/2가 적은 값을 갖게 된다.

 

이런식으로 높이의 상한은 최대값 - N/2 임을 숙지하고 풀도록하자.

 

가장 낮을 수 있는 중간의 높이 0과 최대 높이 H가 있을 때, 각각의 높이에서 움직여야할 블럭의 개수를 구한다. 이때 구한 블럭의 개수를 서로 비교해서 하한높이를 올릴지, 상한높이를 낮출지 정한다.

만약 countBlock(최소높이) >= countBlock(최대높이) 이라면 더 높은 곳에서 더 적게 움직였다는 의미이므로 left = mid + 1로 옮기고, 최소 높이에서의 블럭의 개수를 갱신해준다. (높이를 올림)

반대로 countBlock(최소높이) < countBlock(최대높이) 이라면 더 낮은 곳에서 더 적게 움직였다는 의미이므로 right = mid로 옮기고, 최대 높이에서의 블럭의 개수를 갱신해준다. (높이를 낮춤)

 

🐢코드

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

public class 블럭쌓기_9998 {
    static int N;
    static long[] boardOne;
    static long[] boardTwo;

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

        N = Integer.parseInt(br.readLine());
        boardOne = new long[N];
        boardTwo = new long[N];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            long h1 = Long.parseLong(st1.nextToken());
            boardOne[i] = h1;
            long h2 = Long.parseLong(st2.nextToken());
            boardTwo[i] = h2;
        }

        solution();
    }

    private static void solution() {
        long left = 0;
        long right = (long) Math.pow(10, 12) - N / 2;
        long maxBlockCount = countBlock(right);
        long minBlockCount = countBlock(left);
        long mid;

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

            if (minBlockCount < maxBlockCount) // 낮은 곳 블럭개수가 더 적음. 낮춘다
            {
                right = mid;
                maxBlockCount = countBlock(right);
            } else { // 높은 곳 블럭개수가 더 작거나 같음. 높인다
                left = mid + 1;
                minBlockCount = countBlock(left);
            }
        }
        System.out.println(minBlockCount);
    }

    private static long countBlock(long midH) {
        long total = 0;
        long h = midH;
        for (int i = N / 2; i >= 0; i--) {
            total += Math.abs(boardOne[i] - h);
            total += Math.abs(boardTwo[i] - h);
            h++;
        }
        h = midH + 1;
        for (int i = N / 2 + 1; i < N; i++) {
            total += Math.abs(boardOne[i] - h);
            total += Math.abs(boardTwo[i] - h);
            h++;
        }
        return total;
    }
}

 

🐢 마무리