[백준/Java] 2628번 : 종이자르기

[문제]

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

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

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

[조건]

• 시간 제한 : 1초
• 메모리 제한 : 128MB

[입력]

첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 줄에 점선이 하나씩 아래와 같은 방법으로 입력된다. 가로로 자르는 점선은 0과 점선 번호가 차례로 주어지고, 세로로 자르는 점선은 1과 점선 번호가 주어진다. 입력되는 두 숫자 사이에는 빈 칸이 하나씩 있다.

[출력]

첫째 줄에 가장 큰 종이 조각의 넓이를 출력한다. 단, 넓이의 단위는 출력하지 않는다.

[문제 풀이]

• 가로와 세로를 가르는 점선을 각 배열에 저장, 이를 sort해 정렬함. (rows, columns)
• 배열을 순환하며 가장 긴 구간을 확인 후 변수에 저장. (row, column)
• row * column을 통해 출력

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(br.readLine());
        
        List<Integer> rows = new ArrayList<>(); // 가로 자르는 배열
        List<Integer> columns = new ArrayList<>(); // 세로 자르는 배열
        rows.add(0);
        columns.add(0);
        for(int n=0; n<N; n++) {
            st = new StringTokenizer(br.readLine());
            if(Integer.parseInt(st.nextToken())==1) rows.add(Integer.parseInt(st.nextToken()));
            else columns.add(Integer.parseInt(st.nextToken()));
        }
        rows.add(r);
        columns.add(c);
        Collections.sort(rows);
        Collections.sort(columns);
        
        // 가로와 세로에 대해 각각 반복문 돌며
        // 구간이 가장 큰, 가장 많이 남는 부분 구함
        int row = Integer.MIN_VALUE;
        int column = Integer.MIN_VALUE;
        for(int i=0; i<rows.size()-1; i++) {
        	int num = rows.get(i+1)-rows.get(i);
        	if (num>row) {
        		row = num;
        	}
        }
        for(int i=0; i<columns.size()-1; i++) {
        	int num = columns.get(i+1)-columns.get(i);
        	if (num>column) {
        		column = num;
        	}
        }
        System.out.println(row*column);
    }
}

 

[소감]

아래는 처음 풀이.

문제의 테스트케이스와 직접 만든 테스트케이스에서 문제를 찾지 못해 반례를 생각하는데 시간이 걸림.

아이디어는 다음과 같음.

• 가장 긴 구간의 최소 인덱스(row[0], column[0])와 최대 인덱스(row[1], rolumn[1])를 저장함 (row, column)
• 칼로 잘라야하는 점선의 개수만큼 반복문을 순회
• 잘라야하는 점선이 가로인지 세로인지를 구분
• 가로일 때, 자르는 점선이 row[0]과 row[1] 중 어디에 더 가까운지 절댓값을 통해 확인
• 절댓값이 더 큼 = 더 멀다 = 더 긴 구간
• 이에 따라 row[0], row[1]을 갱신
• column도 동일한 과정 반복

 

반례는?

• 중앙의 점선을 자르는 경우에 대한 처리 부족.
• 점선을 오름차순으로 자르는 것이 아닌, 입력이 들어온 순서대로 잘라주었기 때문에 중앙의 점선을 자르고 난 이후 어느 쪽이 더 긴 쪽이 될지를 결정할 수 없음. 

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

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken()); 
        int c = Integer.parseInt(st.nextToken()); 
        int N = Integer.parseInt(br.readLine());
        
        int[] row = new int[] {0, r};
        int[] column = new int[] {0, c};
        
        for(int n=0; n<N; n++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            if(i==1) {
                if(row[0]<j && j<row[1]) {
                    if(Math.abs(row[0]-j)<Math.abs(row[1]-j)) {
                        row[0] = j;
                    }
                    else {
                        row[1] = j;
                    }
                }
            } else {
                if(column[0]<j && j<column[1]) {
                    if(Math.abs(column[0]-j)<Math.abs(column[1]-j)) {
                        column[0] = j;
                    }
                    else {
                        column[1] = j;
                    }
                }
            }
        }
        System.out.println((row[1]-row[0])*(column[1]-column[0]));
    }
}

 

 

출처 : 백준 https://www.acmicpc.net/problem/2628