Categories: 백준

백준 2628 종이자르기 (자바 Java)

java

백준 2628 종이자르기

문제 정보

문제 링크

문제 출처 : 백준 Baekjoon
문제 번호 : 2628
문제 제목 : 종이자르기
문제 난이도 : 실버5
풀이 언어 : Java

문제

입력으로 종이의 가로 세로 길이, 그리고 잘라야할 점선들이 주어질 때, 가장 큰 종이 조각의 넓이가 몇 ㎠인지를 구하는 프로그램을 작성하시오.

접근

ArrayList 를 활용해 문제를 풀었다.

풀이

스캐너를 사용하여 종이의 가로, 세로 길이와 자르는 횟수를 입력 받는다.
가로 절단선과 세로 절단선을 저장할 ArrayList 두 개를 생성한다.
자르는 방향과 위치에 따라 각 절단선을 해당 리스트에 추가한다.
종이의 가장자리를 나타내는 값 0과 종이의 길이(가로 또는 세로)를 각 리스트에 추가한다.
가로와 세로 절단선 리스트를 오름차순으로 정렬한다.
각 리스트에서 인접한 두 점 사이의 최대 거리를 계산하여 최대 길이를 찾는다.
가로와 세로 절단선에서 계산된 최대 길이를 곱하여 최대 넓이를 계산하고 출력한다.

후기

비슷한 문제를 더 풀어볼 계획이다.

코드

Java

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

public class Main {
 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int width = sc.nextInt();
        int height = sc.nextInt();
        int n = sc.nextInt();

        ArrayList<Integer> horizontalCuts = new ArrayList<>();
        ArrayList<Integer> verticalCuts = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int direction = sc.nextInt();
            int cut = sc.nextInt();

            if (direction == 0) {
                horizontalCuts.add(cut);
            } else {
                verticalCuts.add(cut);
            }
        }

        horizontalCuts.add(0);
        horizontalCuts.add(height);
        verticalCuts.add(0);
        verticalCuts.add(width);

        Collections.sort(horizontalCuts);
        Collections.sort(verticalCuts);

        int maxH = 0, maxV = 0;
        for (int i = 1; i < horizontalCuts.size(); i++) {
            maxH = Math.max(maxH, horizontalCuts.get(i) - horizontalCuts.get(i - 1));
        }
        for (int i = 1; i < verticalCuts.size(); i++) {
            maxV = Math.max(maxV, verticalCuts.get(i) - verticalCuts.get(i - 1));
        }

        System.out.println(maxH * maxV);
 }
}