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

문제

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

<그림 1>

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

<그림 2>

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

입력

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

출력

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

예제 입력 1

10 8
3
0 3
1 4
0 2

예제 출력 1

30

 

소스코드

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

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;

	private static int W, H, N;
	private static Cut[] cut;

	static class Cut {
		int dir, no;

		public Cut(int dir, int no) {
			super();
			this.dir = dir;
			this.no = no;
		}

		@Override
		public String toString() {
			return "Cut [dir=" + dir + ", no=" + no + "]";
		}

	}

	public static void main(String[] args) throws IOException {

		bf = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(bf.readLine());
		W = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(bf.readLine());
		cut = new Cut[N];

		List<Integer> w = new ArrayList<>();
		List<Integer> h = new ArrayList<>();
		w.add(0);
		w.add(W);
		h.add(0);
		h.add(H);
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());
			cut[i] = new Cut(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			if (cut[i].dir == 0)
				h.add(cut[i].no);
			else
				w.add(cut[i].no);
		}

		Collections.sort(w);
		Collections.sort(h);
		
		int width=0, height=0;
		for(int i=1;i<w.size();i++) {
			width=Math.max(width, w.get(i)-w.get(i-1));
		}
		for(int i=1;i<h.size();i++) {
			height=Math.max(height, h.get(i)-h.get(i-1));
		}
		System.out.println(width*height);
	}

}

1. 입력받은 가로와 세로의 길이, 그리고 잘린 경계를 각각 리스트로 만듭니다.

2. 각 리스트를 오름차순 정렬합니다.

3. 정렬된 리스트의 인접한 두 값의 차이를 계산하여 가장 큰 값을 찾습니다.

4. 찾은 가로와 세로 길이를 곱해줍니다.