백준 2628 종이자르기 JAVA 풀이 (구현, 정렬, 시간복잡도)

🔗 문제 링크

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

---

📌 문제 개요

가로 M, 세로 N 크기의 종이를 여러 번 자른다.
각 자르기는 가로(0) 또는 세로(1) 방향으로 이루어진다.

 

모든 자르기가 끝난 후

가장 큰 직사각형 조각의 넓이를 구하는 문제이다.

---

📌 접근 방법

• 가로로 자르면 → 세로 길이가 나뉨
• 세로로 자르면 → 가로 길이가 나뉨

따라서

• 가로선 리스트 (세로 분할)
• 세로선 리스트 (가로 분할)

이렇게 2개로 분리해서 관리한다.

그리고

• 시작점(0)
• 끝점(전체 길이)

을 반드시 포함해야 한다.

---

📌 핵심 아이디어

• 자른 위치들을 정렬
• 인접한 값끼리 차이를 구하면 조각 길이 생성

예 : 0, 2, 3, 8 → 길이: 2, 1, 5

 

가장 큰 길이만 필요

 

최종 결과 : 최대 가로 길이 × 최대 세로 길이

 

---

📌 전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int width = Integer.parseInt(st.nextToken());   // 가로
        int height = Integer.parseInt(st.nextToken());  // 세로
        
        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> row = new ArrayList<>(); // 가로 자르기 (세로 길이)
        ArrayList<Integer> col = new ArrayList<>(); // 세로 자르기 (가로 길이)

        // 시작점, 끝점 추가
        row.add(0);
        row.add(height);
        col.add(0);
        col.add(width);

        for(int i = 0; i < N; i++){
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st1.nextToken());
            int pos = Integer.parseInt(st1.nextToken());

            if(type == 0){
                row.add(pos);
            } else {
                col.add(pos);
            }
        }

        Collections.sort(row);
        Collections.sort(col);

        int maxHeight = 0;
        int maxWidth = 0;

        // 세로 조각 최대
        for(int i = 1; i < row.size(); i++){
            maxHeight = Math.max(maxHeight, row.get(i) - row.get(i - 1));
        }

        // 가로 조각 최대
        for(int i = 1; i < col.size(); i++){
            maxWidth = Math.max(maxWidth, col.get(i) - col.get(i - 1));
        }

        System.out.println(maxWidth * maxHeight);
    }
}

---

📄 정리

• 핵심은 “자른 위치”가 아니라 “구간 길이”
• 정렬 후 인접 차이 계산이 핵심
• 구현 문제지만 아이디어가 중요