[백준 1047] 울타리 - JAVA

BOJ Link

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

 

풀이 과정

나무의 개수 N=40이다. 조합으로 접근할 수 없다.

대신에, 울타리(직사각형의 영역)의 관점에서 생각한다. 나무의 좌표를 정렬한 배열을 통해, 탐색할 모든 영역을 구한다.

이는 총 O(N^5)이며, 나무의 개수가 작으므로 가능하다.

 

1. 어떤 나무들을 모두 포함하는 울타리의 최소 둘레는, (가로변 길이+ 세로변 길이) *2이다. 이를 위해 꼭짓점 좌표 4개를 구해준다. 이 때, 가로/세로 길이가 0이 될수 있으므로 xleft==xright, yleft==yright인 경우도 고려한다. (O(N^4))

 

2. 구성한 울타리를 기준으로, 안에 있는 나무와 밖에 있는 나무를 구해준다. 여기서 밖에 있는 나무란, 사실상 해당 영역을 만들기 위해 자른 나무로 취급한다. 안에 있는 나무는, 밖에 있는 나무로 울타리를 구성할 수 없다면 그리디하게 자르기 위해 pq에 넣어준다. (O(N))

 

3. 밖에 있는 나무들로 현재 울타리를 만들 수 없다면, 안에 있는 나무 중 기대값이 높은 순으로 잘라준다.

(어떤 나무를 잘랐을 때 이 나무가 최외곽이라면, 해당 나무를 둘러쌀 필요가 없어짐에 따라 영역을 재구성 해야 한다고 생각할 수 있다.

하지만 우리는 영역을 기준으로 생각하며 가능한 모든 영역을 구한다. 이는 다른 탐색에서 고려되므로 생각할 필요 없다.)

 

헤맨 부분

조건이 너무 부실하다. 다음은 문제에 해당되는 듯한 조건들이다.

 

1. 울타리는 한 개만 존재해야 한다.

2. 나무가 없다면(= 모두 잘랐다면) 울타리는 없어도 된다.

3. 가로 세로의 길이 중 하나가 0이어도 직사각형이며, 모두 0이어도 직사각형이다. 라는 조건에 의해,

3-1. 나무가 한 개 있다면, 이는 가로/세로 길이가 각각 0인 울타리로 둘러쌓을 수 있다.

3-2. 나무가 일렬로 있다면, 세로 길이가 0인 울타리로 둘러쌓을 수 있다.

 

1번은 유추하기 힘들어서 가정했고,

길이가 0인 직사각형이라는 이상한 개념이 추가되면서 3-1번을 고려하는데 애먹었다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st;

        int[][] tree = new int[N][3];
        int[] treeX = new int[N];
        int[] treeY = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            treeX[i] = tree[i][0] = Integer.parseInt(st.nextToken());
            treeY[i] = tree[i][1] = Integer.parseInt(st.nextToken());
            tree[i][2] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(treeX);
        Arrays.sort(treeY);

        int ans = Integer.MAX_VALUE;
        for (int xl = 0; xl < N; xl++) {
            for (int xr = xl; xr < N; xr++) {
                for (int yl = 0; yl < N; yl++) {
                    for (int yr = yl; yr < N; yr++) {

                        int need = (treeX[xr] - treeX[xl] + treeY[yr] - treeY[yl]) * 2;

                        int cut = 0;
                        int out = 0;
                        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());

                        for (int i = 0; i < N; i++) {
                            if (tree[i][0] >= treeX[xl] && tree[i][0] <= treeX[xr] &&
                                    tree[i][1] >= treeY[yl] && tree[i][1] <= treeY[yr]) {
                                pq.offer(tree[i][2]);
                            } else {
                                out += tree[i][2];
                                cut++;
                            }
                        }
                            while (!pq.isEmpty() && out < need) {
                                out += pq.poll();
                                cut++;
                            }

                            if (out >= need) ans = Math.min(ans, cut);
                    }
                }
            }
        }

        System.out.println(ans);
    }
}