BOJ 16937 두 스티커 (Java)

문제 탐색하기

• 입/출력 개수가 N 최대 100이어서 크지 않기 때문에 완전 탐색으로 풀이가 가능하다.
• 스티커는 90도 회전이 가능하며, 모눈종이를 벗어날 수 없다.
• 2개의 스티커만 붙일 수 있다.

코드 설계하기

1. 모눈종이에 붙일 수 있는 스티커인지 확인한다.
2. 첫 번째 스티커를 확인한다.
   1. 원래 모양대로 붙인다.
   2. 90도 회전해서 붙인다.
3. 두 번째 스티커를 확인한다.
   1. 원래 모양대로
   2. 90도 회전
4. 2, 3의 연산 결과가 기존 최대 넓이보다 크다면 갱신한다.

정답 코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    private static int H, W, N; // 모눈종이 크기, 스티커 수
    private static ArrayList<Sticker> stickers = new ArrayList<>(); // 스티커
    private static int ans = 0; // 정답 저장

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

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

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

        // Sticker 배열 저장
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            if ((h > H && h > W) || (w > W && w > H)) {
                //  붙일 수 없는 경우는 저장하지 않음
                continue;
            }
            stickers.add(new Sticker(h, w)) ;
        }

        checkFirst();

        System.out.println(ans);
    }

    private static void checkFirst() {
        // 첫번째 스티커를 확인한다.

        for (int i = 0; i < stickers.size(); i++) {
            Sticker sticker = stickers.get(i);
            int h = sticker.H, w = sticker.W;

            // 그대로 붙이기
            if (h <= H && w <= W) {
                checkSecond(H - h, W - w, i + 1, sticker.size);
            }

            // 90도 회전
            if (w <= H && h <= W) {
                checkSecond(H - w, W - h, i + 1, sticker.size);
            }
        }
    }

    private static void checkSecond(int newH, int newW, int idx, int size) {
        // 두번째 스티커부터 확인
        for (int i = idx; i < stickers.size(); i++) {
            Sticker sticker = stickers.get(i);
            int h = sticker.H, w = sticker.W;

            // 그대로 붙이기
            if (canPlaceInBoard(newH, newW, h, w)) {
                ans = Math.max(ans, size + sticker.size);
            }

            // 90도 회전
            if (canPlaceInBoard(newH, newW, w, h)) {
                ans = Math.max(ans, size + sticker.size);
            }
        }
    }

    private static boolean canPlaceInBoard(int newH, int newW, int h, int w) {
        return (h <= newH && w <= W) || (h <= H && w <= newW);
    }


    private static class Sticker {
        int H, W, size;

        public Sticker(int H, int W) {
            this.H = H;
            this.W = W;
            size = H * W; // 넓이 저장.
        }
    }

}