[ BOJ ][JAVA][16937] 두 스티커

www.acmicpc.net/problem/16937

16937번: 두 스티커

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	1570	557	410	36.155%

문제

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

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

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

입력

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.

출력

첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다. 두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

제한

• 1 ≤ H, W, N ≤ 100
• 1 ≤ Ri, Ci ≤ 100

예제 입력 1

2 2
2
1 2
2 1

예제 출력 1

4

예제 입력 2

10 9
4
2 3
1 1
5 10
9 11

예제 출력 2

56

예제 입력 3

10 10
3
6 6
7 7
20 5

예제 출력 3

0

코드

/*
    스티커가 나오면 바로 DP가 떠오르지만 이 문제는 아니다!
    시간이 넉넉하고 메모리도 넉넉하다 완전탐색이 제격인 문제로 보인다.
    - 스티커가 90도 회전 가능하지만 스티커의 사이즈가 주어진 형식으로 보아 모든 스티커가 직사각형의 자리를 차지하는 것을 알 수 있다. 
        따라서 하나의 스티커는 두 가지 방식으로 붙일수 있다.
    - 그렇다면 최악의 경우에 100개의 스티커중 2개를 골라 스티커 마다 2가지 방향으로 붙일 수 있으므로 100C2 * 2 * 2로 무난하게 시간제한을 통과할 수 있다.
    - 스티커를 붙일때 마다 돌리지말고 처음부터 붙일수있는 모든 형태의 스티커를 준비하면 편하다.

    - 그러나 90도 회전한 스티커는 원본 스티커와 같기 때문에 두 개의 스티커는 사용되었는지 확인하여 다시 사용하는 일이 없도록 해야한다. (방문체크)
    - 아래에 구현한 코드에서는 Node Class를 스티커의 표현과 시작점의 좌표를 담는데 사용하였다.
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class p16937 {
    static class Node {
        int id;
        int h, w;
        Node (int h, int w, int id) {
            this.h = h;
            this.w = w;
            this.id = id;
        }
    }
    static boolean[][] map;
    static List<Node> list;
    static boolean[] isUsed;
    static int h, w, n, ans;
    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());
        map = new boolean[h][w];
        ans = 0;
        list = new ArrayList<>();
        isUsed = new boolean[n];

        for (int i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());
            int h = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list.add(new Node(h, w, i));
            list.add(new Node(w, h, i));
        }

        go(0, 0);
        System.out.println(ans);
    }

    static void go(int cnt, int size) {
        if (cnt == 2) {
            ans = size > ans ? size : ans;
            return;
        }

        for (Node sticker : list) {
            if(isUsed[sticker.id]) continue;

            Node start = findStart(sticker);

            if (start == null) continue;

            attach(start, sticker, true);
            isUsed[sticker.id] = true;
            go (cnt + 1, size + sticker.h * sticker.w);
            isUsed[sticker.id] = false;
            attach(start, sticker, false);
        }
    }

    static Node findStart(Node sticker) {
        for (int r = 0; r <= h - sticker.h; ++r) {
            for (int c = 0; c <= w - sticker.w; ++c) {
                if (map[r][c]) continue;

                boolean canAttach = true;
                for (int i = r; i < r + sticker.h; ++i) {
                    for (int j = c; j < c + sticker.w; ++j) {
                        if (map[i][j]) {
                            canAttach = false;
                            break;
                        }
                    }
                    if (!canAttach) break;
                }
                if (canAttach) return new Node(r, c, -1);
            }
        }
        return null;
    }

    static void attach(Node start, Node sticker, boolean type) {
        for (int r = start.h; r < start.h + sticker.h; ++r) {
            for (int c = start.w; c < start.w + sticker.w; ++c) {
                map[r][c] = type;
            }
        }
    }
}