[BOJ 2628] 종이자르기

문제

• BOJ 2628
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

이런 유형의 문제는 항상 생각하는게 시간이 오래 걸린다.
오히려 알고리즘을 사용하는 문제면 답이 보이지만, 이런 구현 문제는 어떻게 해결해야 할지 답이 명확히 안보이기 때문에 난이도는 낮지만 더 어렵게 느껴진다.
아마 많이 풀어보면 익숙해지지 않을까 싶다..


이 문제는 처음 생각했을 때 dfs나 bfs로 각 구역을 나눠서 카운팅하려고 했다. 그러나 의외로 간단할것 같은 느낌이 들어서 충분히 고민 후 다른 사람의 코드를 보며 힌트를 얻을 수 있었다.
가로로 자르는 경우 나올 수 있는 최대 길이, 세로로 자르는 경우 나올 수 있는 최대 길이만 구하기 때문에 굳이 2차원 배열을 만들 필요 없이 두가지 경우를 각각 따져보면 된다.
비록 내 아이디어는 아니기 때문에 좀 찜찜한 느낌이 든다. 완전히 내것으로 만들기 위해 이런 유형의 문제를 많이 풀어봐야겠다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int width = Integer.parseInt(st.nextToken());
		int height = Integer.parseInt(st.nextToken());
		
		
		int N = Integer.parseInt(br.readLine()); //점선의 개수
		ArrayList<Integer> row = new ArrayList<>(); //가로로 자르는 경우
		ArrayList<Integer> col = new ArrayList<>(); //세로로 자르는 경우
		
		for(int cnt=1; cnt<=N; cnt++) {
			st = new StringTokenizer(br.readLine());
			int mode = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			
			if(mode == 0) row.add(value);
			else col.add(value);
		}
		
		//끝도 잘라준다.
		row.add(height);
		col.add(width);
		
		Collections.sort(row);
		Collections.sort(col);
		
		//가로로 자르는 경우
		int maxHeight = 0;
		for(int i=0; i<row.size(); i++) {
			if(i==0) maxHeight = row.get(i);
			else maxHeight = Math.max(maxHeight, row.get(i) - row.get(i-1));
		}
		
		//세로로 자르는 경우
		int maxWidth = 0;
		for(int i=0; i<col.size(); i++) {
			if(i==0) maxWidth = col.get(i);
			else maxWidth = Math.max(maxWidth, col.get(i) - col.get(i-1));
		}

		bw.write(maxHeight * maxWidth+"");
		bw.flush();
		bw.close();
		br.close();
	}
}