백준 두 스티커

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다.
다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다.
첫째 줄에 두 스티커가 붙여진 넓이의 최댓값을 출력한다.
두 스티커를 붙일 수 없는 경우에는 0을 출력한다.

내가 이 문제를 보고 생각해본 부분

최대 H * W는 100 * 100 이다.
스티커를 어떻게 붙이던 중요하진않고 붙일 수 있냐 없냐만 중요하다.
스티커는 겹칠 수 없으므로 스티커 넓이 연산은 R * C 로 가능하다.
max_area = Max(Ri * Ci + Rj * Cj)
스티커를 붙일 수 있는지 판단은 두 시티커를 수평으로 붙여보고 수직으로 붙여보면된다.
모든 스티커는 회전 할 수 있다는 것을 가정해야한다.
총 8가지 방법 = A (회전, 무회전) * B(회전, 무회전) * HW( 수평, 수직) 
모든 경우를 따져 통과하는 경우 중 최대 넓이를 출력하면된다.

코드로 구현

package baekjoon.baekjoon_19;

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

// 백준 16937번 문제
public class Main667 {
    static int max_area;
    static int H, W, N;
    static int[][] stickers;

    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().trim());

        stickers = new int[N][3];

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

        max_area = 0;
        calcMax_Area();
        System.out.println(max_area);
    }

    private static void calcMax_Area() {
        for(int i = 0; i < stickers.length; i++) {
            for(int j = i + 1; j < stickers.length; j++) {
                if(i == j)
                    continue;
                if(isCanStick(stickers[i], stickers[j])) {
                    max_area = Math.max(max_area, stickers[i][2] + stickers[j][2]);
                }
            }
        }
    }

    private static boolean isCanStick(int[] a, int[] b) {
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                if((a[i] + b[j]) <= H && Math.max(a[(i+1)%2], b[(j+1)%2]) <= W)
                    return true;
                if((a[i] + b[j]) <= W && Math.max(a[(i+1)%2], b[(j+1)%2]) <= H)
                    return true;
            }
        }
        return false;
    }
}

마무리

실버3문제였지만 어렵게 느껴졌던 문제였다. 이런 문제를 조금더 풀어봐야할것같다.