[BOJ] 2628 종이자르기 - JAVA

1. 문제

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

2628번: 종이자르기

종이를 칼로 자른다.

가로, 세로 방향으로 끝에서 끝까지만 자를 수 있다.

---

2. 풀이

자르는 점선을 모두 입력받고 정렬시켰다.

현재 점선-직전 점선으로 gap을 구해서 하나하나 max값과 비교했다. 맨 끝과의 차이도 알아야 해서 점선 배열에 가로의 끝 값, 세로의 끝 값도 넣어줘야 했다.

하지만 이럴 필요 없이 그냥 가로의 가장 큰 gap, 세로의 가장 큰 gap을 각각 찾아서 서로 곱해주면 된다.

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

public class BOJ_2628_종이자르기 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());

        int width = Integer.parseInt(st.nextToken());
        int height = Integer.parseInt(st.nextToken());

        int N = Integer.parseInt(in.readLine());

        int[][] lines = new int[N + 2][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());
            lines[i][0] = Integer.parseInt(st.nextToken());
            lines[i][1] = Integer.parseInt(st.nextToken());
        }

        lines[N] = new int[]{1, width};
        lines[N + 1] = new int[]{0, height};

        Arrays.sort(lines, (o1, o2) -> o1[1] - o2[1]);

        int maxArea = 0;
        int prevW = 0, prevH;

        for (int i = 0; i < N + 2; i++) {
            if (lines[i][0] != 0) continue;
            int gapW = lines[i][1] - prevW;

            prevH = 0;

            for (int j = 0; j < N + 2; j++) {
                if (lines[j][0] != 1) continue;

                int area = gapW * (lines[j][1] - prevH);
                maxArea = Math.max(maxArea, area);
                prevH = lines[j][1];
            }

            prevW = lines[i][1];

        }

        System.out.println(maxArea);

    }
}

---

3. 결과

대체 왜 넓이를 하나하나 구할 생각을 했는지 모르겠다. 다음엔 안 그래야겠다.