10월 31일 - 코끼리[백준/5823]

• 여러 개의 코끼리 위치를 관리하고 특정 거리 내의 모든 코끼리를 촬영하는 최소 카메라 개수를 계산하는 문제를 풀었다. 이 문제는 각 코끼리의 이동 후마다 최소 카메라 개수를 업데이트해야 해서 빠른 위치 변경과 최적화가 요구된다. 이걸 위해 세그먼트 트리와 버킷 구조를 활용해 문제를 해결했다.

문제 접근 방법

1. 초기화 및 세그먼트 트리 구성:

• 코끼리의 초기 위치와 필요한 카메라 개수를 설정한다. 버킷을 이용해 코끼리 위치를 그룹화하고, 각 버킷이 관측할 수 있는 코끼리 범위(L 내)와 필요한 카메라 개수를 기록한다.

2. 위치 업데이트와 재조정:

• 각 동작 후 이동한 코끼리의 위치를 반영하고, 위치 이동에 따른 카메라 개수 변화 여부를 계산한다.
• update 함수로 특정 위치의 코끼리가 이동하면, 해당 코끼리 위치를 새롭게 정렬하고 다시 필요한 카메라 개수를 업데이트한다.

3. 최소 카메라 개수 계산:

• 모든 코끼리 위치가 주어진 거리 L 내에 포함되도록 최소 카메라 수를 계산하고 업데이트해 출력한다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static final int LEN = 150000;
    static final int SQ = 400;

    static int N, L, M, bLen;
    static int[] pos = new int[LEN];
    static int[] a = new int[LEN];
    static int[] b = new int[LEN];
    static int[] next = new int[SQ * 2];
    static Bucket[] buckets = new Bucket[SQ];

    static class Bucket {
        int size;
        int[] A = new int[SQ * 2];
        int[] cameras = new int[SQ * 2];
        int[] cover = new int[SQ * 2];

        int end() {
            return size > 0 ? pos[A[size - 1]] : 0;
        }

        int bound(int x) {
            int left = 0, right = size - 1, mid;
            int k = size;
            while (left <= right) {
                mid = (left + right) / 2;
                if (pos[A[mid]] > x) {
                    k = Math.min(k, mid);
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            return k;
        }

        void update() {
            for (int l = 0, r = 0; l < size; ++l) {
                while (r < size && pos[A[r]] <= pos[A[l]] + L) ++r;
                next[l] = r;
            }
            for (int r = size - 1; r >= 0; --r) {
                cameras[r] = next[r] == size ? 1 : cameras[next[r]] + 1;
                cover[r] = next[r] == size ? pos[A[r]] + L : cover[next[r]];
            }
        }

        void pop(int elem) {
            int k = -1;
            for (int i = 0; i < size; ++i) {
                if (A[i] == elem) {
                    k = i;
                    break;
                }
            }
            size--;
            for (int i = k; i < size; ++i) A[i] = A[i + 1];
            update();
        }

        void push(int elem) {
            int left = 0, right = size - 1, mid;
            int k = size;
            while (left <= right) {
                mid = (left + right) / 2;
                if (pos[A[mid]] > pos[elem]) {
                    k = Math.min(k, mid);
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            size++;
            for (int i = size - 1; i > k; --i) A[i] = A[i - 1];
            A[k] = elem;
            update();
        }

        void pushBack(int index) {
            A[size++] = index;
        }
    }

    static void init() {
        for (int i = 0; i < bLen; ++i) buckets[i].size = 0;
        for (int i = 0; i < N; ++i) buckets[i / SQ].pushBack(a[i]);
        for (int i = 0; i < bLen; ++i) buckets[i].update();
    }

    static void normalize() {
        for (int i = 0, k = 0; i < bLen; ++i) {
            for (int j = 0; j < buckets[i].size; ++j, ++k) {
                a[k] = buckets[i].A[j];
                b[a[k]] = k / SQ;
            }
        }
        init();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        L = sc.nextInt();
        M = sc.nextInt();
        bLen = N / SQ + 1;

        for (int i = 0; i < N; ++i) {
            pos[i] = sc.nextInt();
            a[i] = i;
            b[i] = i / SQ;
        }

        for (int i = 0; i < bLen; i++) {
            buckets[i] = new Bucket();
        }
        
        init();

        for (int q = 0, j = 0; q < M; ++q, ++j) {
            if (j == SQ - 1) {
                j = 0;
                normalize();
            }
            int index = sc.nextInt();
            int newY = sc.nextInt();
            buckets[b[index]].pop(index);
            pos[index] = newY;
            b[index] = bLen - 1;
            for (int k = 0; k < bLen; ++k) {
                if (newY <= buckets[k].end()) {
                    b[index] = k;
                    break;
                }
            }
            buckets[b[index]].push(index);

            int cameraCount = buckets[0].cameras[0];
            int lastCovered = buckets[0].cover[0];
            for (int k = 1; k < bLen; ++k) {
                if (buckets[k].size == 0 || buckets[k].end() <= lastCovered) continue;
                int boundIndex = buckets[k].bound(lastCovered);
                cameraCount += buckets[k].cameras[boundIndex];
                lastCovered = buckets[k].cover[boundIndex];
            }

            System.out.println(cameraCount);
        }
        sc.close();
    }
}

코드 설명

주요 변수 설명

• LEN과 SQ는 전체 길이와 버킷 수를 정의해 코끼리의 위치 및 버킷 구조의 크기를 설정한다.
• buckets는 각 버킷에 담긴 코끼리의 상태를 저장하며, size, A, cameras, cover 배열로 이루어져 있다.

init 메서드

버킷 초기화와 코끼리 초기 위치 설정을 수행한다. 이후 각 버킷마다 필요한 카메라 개수를 계산해 초기 상태를 완성한다.

normalize 메서드

코끼리의 위치가 정렬되도록 버킷 내 순서를 재조정하고, init 메서드로 초기화를 다시 수행한다.

update 및 push, pop 메서드

update는 각 버킷 내 카메라와 커버 범위를 새롭게 설정해 위치 변경에 따른 카메라 개수 변화를 반영한다.
push는 특정 위치에 코끼리를 추가하며 위치를 갱신한다.
pop은 특정 위치의 코끼리를 제거해 이동 시에도 빠르게 업데이트되도록 돕는다.

So...

어렵지뭐...어려운거지뭐...하지만 코끼리 위치가 자주 변경되므로 위치를 관리하는 데 효율적인 데이터 구조를 선택하는 것이 핵심이었다. 각 버킷마다 필요한 카메라 개수를 계산해 카메라를 최소화하며, 카메라 범위 내에 코끼리가 모두 포함되도록 한 점이 중요한 포인트였다.