[백준] 16937 두 스티커 java

문제

크기가 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

풀이

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

class Point {
    int h;
    int w;
    Point(int h, int w) {
        this.h = h;
        this.w = w;
    }
}

public class Main {
    static BufferedReader br;
    static StringTokenizer st;
    static int H, W, N;
    static List<Point> inputList, pickedList;
    static boolean[] visited;
    static int max;

    public static void main(String[] args) throws IOException {
        init();
        dfs(2, 0);
        System.out.println(max);
    }

    static void init() throws IOException {
        max = 0;
        inputList = new ArrayList<>();
        pickedList = new ArrayList<>();
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        H = stoi(st.nextToken());
        W = stoi(st.nextToken());
        N = stoi(br.readLine());
        visited = new boolean[N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            inputList.add(new Point(stoi(st.nextToken()), stoi(st.nextToken())));
        }

    }

    static void dfs(int p, int start) {
        if(p == 0) {
            int h1 = pickedList.get(0).h;
            int w1 = pickedList.get(0).w;
            int h2 = pickedList.get(1).h;
            int w2 = pickedList.get(1).w;

            //둘 다 그대로인 경우
            if(checkBoundary(h1, w1, h2, w2)) {
                int sum = h1 * w1 + h2 * w2;
                max = Math.max(max, sum);
                return;
            }

            for(int i = 0; i < 3; i++) {
                int a = 0, b = 0, c = 0, d = 0;
                //1만 회전하는 경우
                if(i == 0) {
                    a = w1;
                    b = h1;
                    c = h2;
                    d = w2;
                }
                //2만 회전하는 경우
                if(i == 1) {
                    a = h1;
                    b = w1;
                    c = w2;
                    d = h2;
                }
                //둘 다 회전하는 경우
                if(i == 2) {
                    a = w1;
                    b = h1;
                    c = w2;
                    d = h2;
                }

                if(checkBoundary(a, b, c, d)) {
                    int sum = a * b + c * d;
                    max = Math.max(max, sum);
                    return;
                }
            }
            return;
        }

        //조합
        for(int i = start; i < N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                pickedList.add(inputList.get(i));
                dfs(p-1, i);
                pickedList.remove(pickedList.size()-1);
                visited[i] = false;
            }
        }
    }

    static int stoi(String s) {return Integer.parseInt(s);}

    static boolean checkBoundary(int h1, int w1, int h2, int w2) {
        if(checkUpDown(h1, w1, h2, w2) || checkSide(h1, w1, h2, w2)) return true;
        return false;
    }

    static boolean checkUpDown(int h1, int w1, int h2, int w2) {
        if(h1+h2 > H || Math.max(w1, w2) > W) return false;
        return true;
    }

    static boolean checkSide(int h1, int w1, int h2, int w2) {
        if(Math.max(h1, h2) > H || w1+w2 > W) return false;
        return true;
    }
}

조합 알고리즘을 사용한 완전탐색 문제이다. 경우의 수를 찾는 것이 중요하다.

 

조합으로 뽑은 2개의 스티커를 모두 4가지 모양으로 만들 수 있다.

 

1. 2개다 그대로인 경우

2. 첫번 째 스티커만 회전한 경우

3. 두번 째 스티커만 회전한 경우

4. 둘 다 회전한 경우

 

그리고 각각의 경우에 대해서 위, 아래로 붙인 경우와 양 옆으로 붙인 경우 총 2가지의 경우가 더 있다. 이렇게 총 4 * 2 = 8가지의 경우 중에서 하나라도 모눈종이의 크기를 넘지 않는다면  총 넓이를 구해서 현재 max 값과 비교 후 갱신해주면 된다.