[Java] 백준 종이자르기

1. 문제분석

 

주어진 크기의 종이를 각 번호에 맞게 자르는 문제다.

단순히 생각해서 종이 크기만큼의 배열을 초기화하고 문제를 해결할려고 하면 힘들 것 이다.

나는 자르는 부분의 위치를 기억하고 개수를 더하는 방식으로 해결했다.

 

테스트케이스 1을 보자. 10 * 8의 직사각형이고 세로는 4, 가로는 2, 3을 자른다고 한다.

여기서 볼 점은 3을 자르면 이미 3:7인데 여기서 2를 자른다고 7이 변할까? 이다.

즉, 내가 자르고 남은 것의 가장 큰 가로, 세로를 구해서 곱하면 되는 것이다.

 

세로부터 보자. 4위치를 자른다고 한다. 그렇다면 4 : 6으로 나뉠 것이고 우리는 6을 기억한다.

가로를 보면 3을 먼저 자른다. 3 : 5로 나뉘게 된다. 그 다음 2를 자르면 2 : 1 : 5이 된다.

지금 5가 바뀌었는가? 이미 작은 값에서 자르면 큰 값은 변하지 않는다.

2. 구현

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        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 tc = Integer.parseInt(br.readLine());
        
        //마지막을 구분하기위해 1을 넣어줌
        int[] heightCutPos = new int[width];
        heightCutPos[width - 1] = 1;
        int[] widthCutPos = new int[height];
        widthCutPos[height - 1] = 1;
        
        for (int i = 0; i < tc; i++) {
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int pos = Integer.parseInt(st.nextToken()) - 1;
            if (type == 1) {
                //세로로 자른다 -> 가로를 기록
                heightCutPos[pos] = 1;
            } else {
                //가로로 자른다 -> 세로를 기록
                widthCutPos[pos] = 1;
            }
        }
        /**
         * 초기값은 0으로 해야함, 그래야 연속된 자리도 1로 기록
         * (0, 1, 1, 0, 1) -> 2 : 1 : 2
         * */
        int widthCount = 1, heightCount = 1;
        int maxWidth = 0, maxHeight = 0;
        for (int i = 0; i < width; i++) {
            if (heightCutPos[i] == 1) {
                maxWidth = Math.max(maxWidth, widthCount);
                widthCount = 1;
            } else {
                widthCount++;
            }
        }
        for (int i = 0; i < height; i++) {
            if (widthCutPos[i] == 1) {
                maxHeight = Math.max(maxHeight, heightCount);
                heightCount = 1;
            } else {
                heightCount++;
            }
        }
        System.out.println(maxHeight * maxWidth);
    }
}

widthCutPos와 heightCutPos는 가로를 자르는 지점, 세로를 자르는 지점이다.

즉, 가로를 자른다고 하면 세로의 인덱스에서 기록해야하고 세로를 자른다고 하면 가로의 인덱스에서 잘라야한다.

또한, widthCount와 heightCount의 기본값을 1로 했는데 연속적인 1이 나와도 1칸으로 기록하기 때문에 1로 초기화했다.

3. 마무리

첫 시작을 2차원 배열을 만들어서 어쩌구 저쩌구 하려고 보니 너무 복잡해 졌다.

생각해보니 자르는 부분을 기록하면 되는 문제였고 가로 자르는 위치는 세로의 인덱스를 넣어줘야하는게 헷갈려서 시간이 좀 걸렸다.