[BOJ] 백준 9998 : 블록 쌓기 (java)

🧪 9998 블록 쌓기

---

난이도 : 🌟 골드 3
유형 : 이분탐색

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

 

📝 문제

---

 

윤형이와 동혁이가 블록 쌓기 놀이를 한다. 두 명 모두 너비 N의 블록 건물을 쌓았는데, 윤형이는 k번째 열에 Yk개의 블록을 쌓았고 동혁이는 k번째 열에 Dk개의 블록을 쌓았다. 윤형이와 동혁이는 블록을 쌓거나 빼면서 두 개의 똑같은 건물을 만들려고 한다.

한편, 이 둘이 새로 만들려는 건물은 위 그림의 오른쪽 형태와 같이 팩맨 모양이 되어야 한다. 즉, 왼쪽에서 오른쪽으로 갈수록 블록의 개수가 감소하다가 증가하는 꼴이 되어야 한다. 또, 인접한 두 열의 블록의 개수는 정확히 한 개씩만 차이나야 하며, 블록의 개수가 가장 적은 열은 정중앙이여야 한다.

방을 어지르지 않기 위해서, 블록을 하나 뺐으면 바로 블록 상자에 넣는다. 블록을 다른 곳으로 옮겨야 한다면, 블록을 상자에 넣었다가 빼서 원하는 곳에 쌓아야 한다. 블록 상자에는 무한히 많은 블록이 있다.

윤형이와 동혁이가 원하는 방법으로 블록 건물을 바꿀 때, 블록을 빼거나 쌓는 횟수를 최소화하는 프로그램을 작성하여라.

 

 

입력

 

첫 번째 줄에는 두 블록 건물의 너비 N이 주어진다. N은 홀수이다.

두 번째 줄에는 윤형이의 블록 건물의 높이 Yk가 주어진다.

세 번째 줄에는 동혁이의 블록 건물의 높이 Dk가 주어진다.

 

출력

 

블록을 쌓거나 빼는 작업의 수의 최솟값을 출력한다.

 

🧐 핵심 로직

---

1. BufferedReader를 통해 입력 데이터를 읽어들이고, n과 blockD, blockY 배열을 초기화한다. 입력은 파일에서 읽으며, 두 줄로 이루어진 숫자 데이터를 StringTokenizer를 사용해 파싱하여 blockD와 blockY 배열에 저장한다.

 

2. binarySearch 메서드를 호출하여 최소 블록 이동 횟수를 계산하는 과정을 시작한다. 이진 탐색 범위는 0부터 10^{12} - n/2 까지로 설정되며, 초기 minBlockCount와 maxBlockCount를 계산한다. ( V자 형태이고 인접한 블록이 한 개씩만 차이가 나야하기 때문에 가운데 열에 올 수 있는 최대의 높이가 위와 같이 된다. )

 

3. 이진 탐색 루프에서 mid 값을 계산하고, countBlock 메서드를 호출해 mid 값을 기준으로 블록 이동 횟수를 비교한다. minBlockCount와 maxBlockCount 값을 바탕으로 left와 right 범위를 조정한다.

 

4. 탐색이 종료된 후 maxBlockCount 값을 출력한다. 이는 블록 배열을 특정 목표 높이로 정렬하는 데 필요한 최소 총 블록 이동 횟수를 의미한다.

 

5. countBlock 메서드는 주어진 목표 높이 target에 대해 블록들을 정렬하는 데 필요한 이동 횟수를 계산한다. 중앙값을 기준으로 왼쪽과 오른쪽 배열을 각각 target부터 증가하는 높이에 맞춘다. 이 과정에서 Math.abs를 사용해 각 블록의 이동 횟수를 합산한다.

 

6. 전체 코드의 구조는 이진 탐색을 통해 정렬 목표 높이를 효율적으로 찾고, countBlock으로 이동 비용을 계산하여 최적의 결과를 도출하는 방식으로 설계되어 있다.

 

💻 최종 코드 (536 ms)

---

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

public class Main {

    static int n;
    static long[] blockD;
    static long[] blockY;
    public static void main(String[] args) throws Exception {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        n = Integer.parseInt(br.readLine());
        blockD = new long[n];
        blockY = new long[n];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            blockD[i] = Long.parseLong(st1.nextToken());
            blockY[i] = Long.parseLong(st2.nextToken());
        }

        binarySearch();
        
        br.close(); 
    }

    private static void binarySearch() {

        long left = 0;
        long right = (long) Math.pow(10, 12) - (n / 2);
        long minBlockCount = countBlock(left);
        long maxBlockCount = countBlock(right);

        while (left < right) {

            long mid = (left + right) / 2;

            if (minBlockCount < maxBlockCount) {
                right = mid;
                maxBlockCount = countBlock(right);
            } else {
                left = mid + 1;
                minBlockCount = countBlock(left);
            }
        }

        System.out.println(maxBlockCount);
    }

    private static long countBlock(long target) {

        long totalBlock = 0;
        long h = target;
        for (int i = n / 2; i >= 0; i--) {
            totalBlock += Math.abs(blockD[i] - h);
            totalBlock += Math.abs(blockY[i] - h);
            h++;
        }

        h = target + 1;
        for (int i = n / 2 + 1; i < n; i++) {
            totalBlock += Math.abs(blockD[i] - h);
            totalBlock += Math.abs(blockY[i] - h);
            h++;
        }

        return totalBlock;
    }
}