BOJ_2628 : 종이자르기

👉 문제링크

2628번: 종이자르기

---

---

🔸 문제 분석 🔸

• 종이 크기와 자르는 정보를 입력받고, 잘린 종이 중 가장 큰 면적을 출력한다.
• 0, 0부터 순서대로 좌표를 바꿔가며 접근하므로 가로 컷팅, 세로 컷팅 정보가 따로 정렬이 필요하다.
  • 면적을 구하는 문제이므로 좌표의 크기 차이로 계산하는게 수월하다.

🔸 코드 🔸

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 r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(br.readLine());
        ArrayList<Integer> row = new ArrayList<>();
        ArrayList<Integer> col = new ArrayList<>();

        for (int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            if (Integer.parseInt(st.nextToken()) == 0)
                row.add(Integer.parseInt(st.nextToken()));
            else
                col.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(row);
        Collections.sort(col);

        int answer = 0;
        int x = 0, y = 0;
        for (int i = 0; i <= row.size(); i++){
            int xx = 0, yy;
            for (int j = 0; j <= col.size(); j++){
                if (i == row.size()){
                    xx = c;
                }else xx = row.get(i);
                if (j == col.size()){
                    yy = r;
                }else yy = col.get(j);

                int temp = (xx-x)*(yy-y);
                if (temp > answer) answer = temp;

                if (j != c)
                    y = yy;
            }
            y = 0;
            if (i != r)
                x = xx;
        }
        System.out.println(answer);
    }
}

🔸 코드 해석 🔸

• 종이 크기와 n개의 가로 세로 컷팅 정보를 입력 받는다.
  • 가로 세로의 컷팅 정보는 ArrayList에 담고 오름차순 정렬한다.
• 좌상단 좌표 x, y와 우하단 좌표 xx, yy의 차이로 너비를 계산하며, 최대값 answer를 저장한다.
  • 좌표는 xx가 다음 x가 되고 yy가 다음 y가 되는 방식이다.
  • 마지막 xx, yy는 종이의 끝 좌표를 넣어야 한다.

---

🔸 end 🔸

• 생각보다 문제 풀이의 키 포인트를 못잡았는데, 정렬이 핵심 풀이 조건이었다.