[16937] 두 스티커

🔗 문제 링크

https://www.acmicpc.net/problem/16937

🔍 문제 설명

크기가 H×W인 모눈종이와 스티커 N개가 있다. i번째 스티커의 크기는 Ri×Ci이다. 모눈종이는 크기가 1×1인 칸으로 나누어져 있으며, 간격 1을 두고 선이 그어져 있다.

오늘은 모눈종이에 스티커 2개를 붙이려고 한다. 스티커의 변은 격자의 선과 일치하게 붙여야 하고, 두 스티커가 서로 겹치면 안 된다. 단, 스티커가 접하는 것은 가능하다. 스티커를 90도 회전시키는 것은 가능하다. 스티커가 모눈종이를 벗어나는 것은 불가능하다.

두 스티커가 붙여진 넓이의 최댓값을 구해보자.

⚠️ 제한사항

• 1 ≤ H, W, N ≤ 100

• 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

---

🗝 풀이 (언어 : Java)

단순한 구현 문제이다. 전체 케이스를 모두 돌아도 9900개의 케이스라 시간 복잡도 제한에 걸리지 않는다.

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int H = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(br.readLine());
        int[][] stickers = new int[n][2];
        for (int i = 0; i < n; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            stickers[i][0] = Integer.parseInt(st2.nextToken());
            stickers[i][1] = Integer.parseInt(st2.nextToken());
        }
        br.close();
        solution(H, W, stickers);
    }

    private static void solution(int H, int W, int[][] stickers) {
        int max = 0;
        for (int i = 0; i < stickers.length - 1; i++) {
            int R1 = stickers[i][0];
            int C1 = stickers[i][1];
            for (int j = i + 1; j < stickers.length; j++) {
                int R2 = stickers[j][0];
                int C2 = stickers[j][1];
                if (check(H, W, R1, R2, C1, C2)) {
                    max = Math.max(max, R1 * C1 + R2 * C2);
                }
                if (check(H, W, C1, R2, R1, C2)) {
                    max = Math.max(max, R1 * C1 + R2 * C2);
                }
                if (check(H, W, R1, C2, C1, R2)) {
                    max = Math.max(max, R1 * C1 + R2 * C2);
                }
                if (check(H, W, C1, C2, R1, R2)) {
                    max = Math.max(max, R1 * C1 + R2 * C2);
                }
            }
        }
        System.out.println(max);
    }

    private static boolean check(int H, int W, int r1, int r2, int c1, int c2) {
        if ((c1 + c2) <= H && Math.max(r1, r2) <= W) {
            return true;
        }
        if ((c1 + c2) <= W && Math.max(r1, r2) <= H) {
            return true;
        }
        return false;
    }

}