[백준 실버 5] 2628번: 종이자르기

문제

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

2628번: 종이자르기

 

 

풀이

• 직사각형 모양의 모눈종이가 있다. 1cm마다 점선으로 표시되어 있고, 각 점선에는 순서대로 번호가 부여되어 있다.
• 직사각형의 가로와 세로의 길이, 그리고 잘라야하는 점선이 주어질 때, 가장 큰 종이 조각의 넓이를 구해야 한다.

가로로 잘라야 하는 점선과 세로로 잘라야 하는 점선을 각각 ArrayList로 입력 받은 다음 순서대로 정렬해서 문제를 해결하였다.

길이를 구해야하므로 처음과 끝도 ArrayList에 넣어주었다.

ArrayList<Integer> row = new ArrayList<>();
ArrayList<Integer> column = new ArrayList<>();

for (int t = 0; t < T; t++) {
    st = new StringTokenizer(br.readLine());
    int type = Integer.parseInt(st.nextToken());
    int a = Integer.parseInt(st.nextToken());

    if (type == 0) {
        row.add(a);
    } else if (type == 1) {
        column.add(a);
    }
}

row.add(0);
row.add(M);
column.add(0);
column.add(N);

Collections.sort(row);
Collections.sort(column);

 

각각의 리스트를 탐색하며 현재 가리키는 값과 이전 값의 차가 바로 종이를 잘랐을 때 한 변의 길이가 된다. 이때 구할 수 있는 최대값을 서로 곱하면 최대 넓이가 된다.

int maxRow = 0;
for (int i = 1; i < row.size(); i++) {
    maxRow = Math.max(maxRow, row.get(i) - row.get(i - 1));
}

int maxColumn = 0;
for (int i = 1; i < column.size(); i++) {
    maxColumn = Math.max(maxColumn, column.get(i) - column.get(i - 1));
}

System.out.println(maxRow * maxColumn);

 

 

 

전체 코드 (Java)

import java.io.BufferedReader;
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 Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(br.readLine());

		ArrayList<Integer> row = new ArrayList<>();
		ArrayList<Integer> column = new ArrayList<>();

		for (int t = 0; t < T; t++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());

			if (type == 0) {
				row.add(a);
			} else if (type == 1) {
				column.add(a);
			}
		}

		row.add(0);
		row.add(M);
		column.add(0);
		column.add(N);

		Collections.sort(row);
		Collections.sort(column);

		int maxRow = 0;
		for (int i = 1; i < row.size(); i++) {
			maxRow = Math.max(maxRow, row.get(i) - row.get(i - 1));
		}

		int maxColumn = 0;
		for (int i = 1; i < column.size(); i++) {
			maxColumn = Math.max(maxColumn, column.get(i) - column.get(i - 1));
		}

		System.out.println(maxRow * maxColumn);

	}

}

 

 

후기

처음에는 직사각형의 모든 변을 탐색하는 코드를 생각하였지만 자르는 부분만 생각하는 방법이 더 효율적이었다.