백준저지 2628번 종이자르기

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

2628번: 종이자르기

 

제출 날짜: 2021년 8월 23일 월요일

 

 

 

생각

당연히 한 번에 맞을 줄 알았는데 런타임에러(IndexOutOfBounds)가 났다. 이유를 전혀 모르겠어서 검색을 해보니 나와 같은 경우의 질문(https://www.acmicpc.net/board/view/27994)을 발견했다. 한번도 자르지 않는 경우는 생각을 못했기 때문에 틀린 거였다. 

해당 답변에서 문제를 풀 때, 주어진 테스트케이스만 해볼 것이 아니라 추가적인 반례로 최소값과 입력값 변화를 추천했는데 나도 그렇게 해봐야겠다.

 

 

 

코드

// 출처: 백준저지 2628번 종이자르기 https://www.acmicpc.net/problem/2628

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class BOJ2628 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int W = sc.nextInt(); // 가로
		int H = sc.nextInt(); // 세로
		int N = sc.nextInt(); // 점선 개수
		ArrayList<Integer> widthCut = new ArrayList<>();
		ArrayList<Integer> heightCut = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			int wh = sc.nextInt();
			int len = sc.nextInt();
			if (wh == 0) { // 가로
				widthCut.add(len);
			} else { // 세로
				heightCut.add(len);
			}
		}
		int maxW = getMaxLen(H, widthCut); // 세로 y축 기준으로 자르기
		int maxY = getMaxLen(W, heightCut); // 가로 x축 기준으로 자르기

		System.out.println(maxW * maxY); // 답 출력
	}

	private static int getMaxLen(int N, ArrayList<Integer> cuts) { // N은 길이, cuts는 점선
		int cutCnt = cuts.size();
		if (cutCnt == 0) { // 한번도 잘리지 않은 경우
			return N;
		}
		Collections.sort(cuts); // 정렬

		int max = cuts.get(0); // 처음 잘린 길이가 우선 제일 크다고 초기화
		for (int i = 1; i < cutCnt; i++) { // 첫번째와 두번째 차이, ...
			max = Math.max(max, cuts.get(i) - cuts.get(i - 1));
		}
		max = Math.max(max, N - cuts.get(cutCnt - 1)); // 마지막 잘린 것 길이

		return max;
	}

}