백준 - 2628번(종이자르기)

문제 출처: https://www.acmicpc.net/problem/2628

---

아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으로 번호가 붙어 있다.

<그림 1>

점선을 따라 이 종이를 칼로 자르려고 한다. 가로 점선을 따라 자르는 경우는 종이의 왼쪽 끝에서 오른쪽 끝까지, 세로 점선인 경우는 위쪽 끝에서 아래쪽 끝까지 한 번에 자른다. 예를 들어, <그림 1>의 가로 길이 10㎝이고 세로 길이 8㎝인 종이를 3번 가로 점선, 4번 세로 점선, 그리고 2번 가로 점선을 따라 자르면 <그림 2>와 같이 여러 개의 종이 조각으로 나뉘게 된다. 이때 가장 큰 종이 조각의 넓이는 30㎠이다.

<그림 2>

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

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

        int hori = Integer.parseInt(tokenizer.nextToken()); // 가로
        int vert = Integer.parseInt(tokenizer.nextToken()); // 세로

        List<Integer> horiCut = new ArrayList<>();
        List<Integer> vertCut = new ArrayList<>();

        int N = Integer.parseInt(reader.readLine()); // 자르는 점선의 개수
        for (int i = 0; i < N; i++) { // 가로, 세로로 자르는 라인수를 각각 맞게 저장
            tokenizer = new StringTokenizer(reader.readLine());
            if (Integer.parseInt(tokenizer.nextToken()) == 0) horiCut.add(Integer.parseInt(tokenizer.nextToken()));
            else vertCut.add(Integer.parseInt(tokenizer.nextToken()));
        }

        // 리스트 정렬
        Collections.sort(horiCut);
        Collections.sort(vertCut);

        int result = 0;

        int row = 0; // 직전 행
        for (int i = 0; i < horiCut.size(); i++) {
            int col = 0; // 직전 열
            for (int j = 0; j < vertCut.size(); j++) {
                int area = (horiCut.get(i) - row) * (vertCut.get(j) - col);
                col = vertCut.get(j);
                result = Math.max(result, area);
            }

            if (vertCut.size() > 0) {
                // 마지막 열 처리
                int area = (horiCut.get(i) - row) * (hori - vertCut.get(vertCut.size() - 1));
                result = Math.max(result, area);
            }

            // 세로로 안자르는 경우
            if (vertCut.size() == 0) {
                int area = (horiCut.get(i) - row) * hori;
                result = Math.max(result, area);
            }

            row = horiCut.get(i);
        }

        if (horiCut.size() > 0) {
            // 마지막 행 처리
            int col = 0; // 직전 열
            for (int j = 0; j < vertCut.size(); j++) {
                int area = (vert - horiCut.get(horiCut.size() - 1)) * (vertCut.get(j) - col);
                col = vertCut.get(j);
                result = Math.max(result, area);
            }

            if (vertCut.size() > 0) {
                // 마지막 열 처리
                int area = (vert - horiCut.get(horiCut.size() - 1)) * (hori - vertCut.get(vertCut.size() - 1));
                result = Math.max(result, area);
            }

            // 세로로 안자르는 경우
            if (vertCut.size() == 0) {
                int area = (vert - horiCut.get(horiCut.size() - 1)) * hori;
                result = Math.max(result, area);
            }
        }

        // 가로로 안자르는 경우
        if (horiCut.size() == 0) {
            int col = 0; // 직전 열
            for (int j = 0; j < vertCut.size(); j++) {
                int area = vert * (vertCut.get(j) - col);
                col = vertCut.get(j);
                result = Math.max(result, area);
            }

            if (vertCut.size() > 0) {
                // 마지막 열 처리
                int area = vert * (hori - vertCut.get(vertCut.size() - 1));
                result = Math.max(result, area);
            }
        }

        System.out.println(result);
    }

}

---

• 가로, 세로로 자르는 인덱스를 따로 리스트에 저장한 뒤, 정렬하여 작은 것부터 처리한다.