[백준] 16937 두 스티커 JAVA

📌 문제 탐색하기

문제 링크 : https://www.acmicpc.net/problem/16937

• H : 모눈종이의 높이

• W : 모눈종이의 너비

• N : 스티커의 개수

• i 번째 스티커의 크기 : $R_i * C_i$

• 스티커를 90도 회전시킬 수 있고, 두 스티커는 서로 겹쳐서도 안되고, 모눈 종이를 벗어나서도 안된다

• 두 스티커를 붙였을 때 최대로 차지하는 넓이를 구해야 함! 핵심!!

알고리즘 선택

스티커의 조합이 가장 큰 넓이를 가지는 지 전부 탐색과 비교가 필요함 → 브루트포스 알고리즘 사용

가능한 시간복잡도

스티커 조합 생성할때 $O(N^2)$ 시간 복잡도를 가지게 ehla → 각 배치 방법을 확인하는 데 O(1) 시간이 걸리면 문제를 해결할 수 있다.

📌 코드 설계하기

1. 문제의 input을 받는다, 배열에 스티커의 크기를 저장

2. 모눈종이보다 큰 스티커가 있다면 스티커로 사용할 수 없다. (배열에서 제외)

3. 완전 탐색

   1. 첫번째로 붙일 스티커 선택하기

   2. 두번째로 붙일 스티커 선택하기

      스티커의 너비의 합을 계산후, 최대 넓이보다 크다면 update한다

📌 시도 회차 수정 사항

1회차

• 90도 회전을 어떻게 설계해야 할지 몰랐다. (2,4) 라면 (4,2)가 가능해지는 것 → case 변수를 생성하였다.
  

2회차

• 두스티커의 단순 가로와 세로합의 조합으로 스티커가 가능하다, 불가능하다를 판단했음

      static boolean canPlace(int r1, int c1, int r2, int c2) {
          return (r1 + r2 <= H && Math.max(c1, c2) <= W) ||  // 세로
                  (c1 + c2 <= W && Math.max(r1, r2) <= H);   // 가로
      }

• 스티커를 한개 배치후 남은 공간에 배치 하는 것으로 변경

📌 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    static int H, W, N;
    static int[][] sticker;

    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());
        N = Integer.parseInt(br.readLine());

        sticker = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            sticker[i][0] = Integer.parseInt(st.nextToken());
            sticker[i][1] = Integer.parseInt(st.nextToken());
        }
        int maxArea = 0;

        for (int i = 0; i < N; i++) {
            if (sticker[i][0] > H && sticker[i][1] > W) continue;
            for (int j = i + 1; j < N; j++) {
                if (sticker[j][0] > H && sticker[j][1] > W) continue;
                maxArea = Math.max(maxArea, getStickerArea(sticker[i], sticker[j]));
            }
        }

        System.out.println(maxArea);
    }

    // 최대 너비 계산
    static int getStickerArea(int[] s1, int[] s2) {
        int max = 0;
        int[][] stickers = {
                {s1[0], s1[1]}, {s1[1], s1[0]}, // 회전을 한 경우도 포함 ![](https://velog.velcdn.com/images/dayon_log/post/bccec05e-d93d-4f68-9e2e-31aafc787811/image.jpg)

                {s2[0], s2[1]}, {s2[1], s2[0]}  
        };

        for (int k = 0; k < 2; k++) {
            for (int l = 2; l < 4; l++) {
                int x1 = stickers[k][0], y1 = stickers[k][1];
                int x2 = stickers[l][0], y2 = stickers[l][1];

                max = getMax(max, x1, y1, x2, y2, x1 * y1, x2 * y2);

                max = getMax(max, y1, x1, y2, x2, x1 * y1, x2 * y2);
            }
        }

        return max;
    }

    private static int getMax(int max, int x1, int y1, int x2, int y2, int i, int i2) {
        if (x1 <= H && y1 <= W) {
            // 첫 번째 스티커를 붙이고, 남은 아래 부분에 두번째 스티커가 들어가는 경우
            if (x2 <= H && y2 <= W - y1) {
                max = Math.max(max, i + i2);
            }
            // 첫 번째 스티커를 붙이고, 남은 오른쪽 부분에 두번째 스티커가 들어가는 경우
            if (x2 <= H - x1 && y2 <= W) {
                max = Math.max(max, i + i2);
            }
        }
        return max;
    }

}