[파이썬, 자바] BOJ_2628(종이자르기)

문제

 

www.acmicpc.net/problem/2628

2628번: 종이자르기

---

 

해설

 

가로, 세로로 종이를 잘라서 생긴 사각형들 중 가장 큰 사각형 조각을 찾는 문제이다.

 

type이 0이면 가로로 자르는 것이고

1이면 세로로 자르는 것이다.

 

잘려진 각 사각형의 가로, 세로 길이를 구해 곱해주면 넓이를 구할 수 있다.

더 넓은 조각이 나올 때 마다 resMax 값을 교체해주면 된다.

---

코드

 

-파이썬

#백준 2628(종이자르기)

x, y = map(int, input().split())  #가로, 세로
n = int(input())  #자르는 횟수
x_list = [0, x]  #가로 자르는 곳(세로선)
y_list = [0, y]  #세로 자르는 곳(가로선)

for _ in range(n):
    type, point = map(int, input().split())
    if type == 0:  #가로로 자름
        y_list.append(point)
    else:  #세로로 자름
        x_list.append(point)

x_list.sort()
y_list.sort()

resMax = 0  #가장 큰 조각의 넓이
for i in range(1, len(x_list)):
    for j in range(1, len(y_list)):
        width = x_list[i] - x_list[i - 1]
        height = y_list[j] - y_list[j - 1]
        resMax = max(resMax, width * height)  #가장 큰 조각의 넓이

print(resMax)

 

-자바

//백준 2628(종이자르기)
import java.util.*;
import java.io.*;

public class Boj_2628 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		List<Integer> x_arrList = new ArrayList<Integer>();  //가로 자르는 곳(세로선)
		List<Integer> y_arrList = new ArrayList<Integer>();  //세로 자르는 곳(가로선)
		
		x_arrList.add(Integer.parseInt(st.nextToken()));  //가로(마지막 점도 추가)
		y_arrList.add(Integer.parseInt(st.nextToken()));  //세로
		x_arrList.add(0);
		y_arrList.add(0);
		
		st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());  //자르는 횟수
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());  //가로, 세로
			int point = Integer.parseInt(st.nextToken());  //자르는 점
			
			if(type == 0) {  //가로로 자름
				y_arrList.add(point);
			}
			else {  //세로로 자름
				x_arrList.add(point);
			}
		}
		
		Collections.sort(x_arrList);
		Collections.sort(y_arrList);
		
		int width = 0;
		int height = 0;
		int resMax = 0;  //가장 큰 조각의 넓이
		for(int i = 1; i < x_arrList.size(); i++) {
			for(int j = 1; j < y_arrList.size(); j++) {
				width = x_arrList.get(i) - x_arrList.get(i - 1);
				height = y_arrList.get(j) - y_arrList.get(j - 1);
				resMax = Math.max(resMax, width * height);  //가장 큰 조각의 넓이
			}
		}
		
		System.out.println(resMax);
	}

}