anott
기록
anott
  • 분류 전체보기
    • 오라클
    • SQL
    • 알고리즘
      • 백준저지
      • 프로그래머스
      • SWEA
    • 개발 관련
    • 프론트엔드
      • TypeScript, Next.js
      • React 공식문서 읽기
hELLO · Designed By 정상우.
anott

기록

백준저지 2628번 종이자르기
알고리즘/백준저지

백준저지 2628번 종이자르기

2021. 8. 24. 23:06

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

 

2628번: 종이자르기

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

www.acmicpc.net

 

제출 날짜: 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;
	}

}

 

저작자표시 비영리 (새창열림)

'알고리즘 > 백준저지' 카테고리의 다른 글

백준저지 2116번 주사위 쌓기  (0) 2021.08.26
백준저지 2527번 직사각형  (0) 2021.08.25
백준저지 14696번 딱지놀이  (0) 2021.08.23
백준저지 13300번 반 배정  (0) 2021.08.21
백준저지 2304번 창고 다각형  (0) 2021.08.20
    '알고리즘/백준저지' 카테고리의 다른 글
    • 백준저지 2116번 주사위 쌓기
    • 백준저지 2527번 직사각형
    • 백준저지 14696번 딱지놀이
    • 백준저지 13300번 반 배정
    anott
    anott

    티스토리툴바