[백준] 2628. 종이자르기 (Java)

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

2628번: 종이자르기

 

 

풀이

0. 문제해석

처음에는 x * y 배열을 만들어 안 자른 곳을 0, 자른 곳을 1로 해서

0이 붙어있는 최대 갯수를 출력하려고 했는데, 탐색 부분이 비효율적이기 때문에 다른 방법을 구상하였다.

 

가장 큰 종이조각의 넓이만 출력하면 되므로 문제를 잘 살펴보면 

가로로 자르는 번호와 세로로 자르는 번호를 각각 정렬한 후,

잘랐을 때 이전 번호와 비교하여 몇칸이 나오는지를 전부 비교하여

가장 크게 나오는 세로 길이, 가장 크게 나오는 가로 길이를 곱해주면 정답을 구할 수 있다.

 

위 예시의 경우

가로로 2,3 번을 짤랐을때 

0~2 (2) / 2~3 (1) / 3~8 (5) 으로 가장 긴 세로길이는 5이고

 

세로로 4 번을 짤랐을 때

0~4 (4) / 4~10 (6) 으로 가장 긴 가로 길이는 6이기 때문에

정답은 5 * 6 = 30 이 된다.

 

1. 가로, 세로 자르기 번호 정렬

각각 번호를 저장할 ArrayList를 생성해주고

비교를 위한 처음, 마지막 선을 추가해준 후

들어온 타입에 따라 가로, 세로 리스트에 넣어정렬 해준다.

 

2. 간격 비교하여 최대값 찾기

0번 줄부터 시작하여

다음 자르는 번호까지의 간격을 계산하여,

최대 간격을 구한다.

 

3. 전체코드

// [백준] 2628. 종이자르기 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Solution {
	static int x; // 가로 길이
	static int y; // 세로 길이
	static int n; // 점선 개수
	static int maxX; // 최대 가로 길이
	static int maxY; // 최대 세로 길이
	static ArrayList<Integer> colCutList = new ArrayList<>(); // 세로로 자르기
	static ArrayList<Integer> rowCutList = new ArrayList<>(); // 가로로 자르기

    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	StringTokenizer st = new StringTokenizer(br.readLine());
    	x = Integer.parseInt(st.nextToken());
    	y = Integer.parseInt(st.nextToken());

    	// 처음, 마지막 선 추가
    	colCutList.add(0);
    	colCutList.add(x);
    	rowCutList.add(0);
    	rowCutList.add(y);

    	n = Integer.parseInt(br.readLine());
    	// 자르기 입력
    	for(int i = 0; i < n; i++) {
    		st = new StringTokenizer(br.readLine());
    		int type = Integer.parseInt(st.nextToken()); // 자르는 점선 타입

    		// 가로로 자르기
    		if(type == 0) {
    			rowCutList.add(Integer.parseInt(st.nextToken()));
    		}
    		// 세로로 자르기
    		else if(type == 1) {
    			colCutList.add(Integer.parseInt(st.nextToken()));
    		}
    	}

    	// 정렬
    	Collections.sort(colCutList);
    	Collections.sort(rowCutList);

    	rowCut();
    	colCut();
    	System.out.println(maxX * maxY);

    	br.close();
    }

    // 가로로 자르기
    public static void rowCut() {
    	for(int i = 0; i < rowCutList.size() - 1; i++) {
    		int dis = rowCutList.get((i+1)) - rowCutList.get(i); // 두 점 사이의 거리
    		maxY = Math.max(maxY, dis); // 간격 가장 넓은 것 찾기
    	}
    }

    // 세로로 자르기
    public static void colCut() {
    	for(int i = 0; i < colCutList.size() - 1; i++) {
    		int dis = colCutList.get((i+1)) - colCutList.get(i); // 두 점 사이의 거리
    		maxX = Math.max(maxX, dis); // 간격 가장 넓은 것 찾기
    	}
    }
}