[알고리즘] 16937번

오늘 풀어볼 문제는 백준 16937번 문제 "두 스티커" 이다.

이 문제는 실버3 문제이고 브루트 포스 문제이다.

문제

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

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

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

입력

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

출력

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

📌첫 번째 시도📌

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

public class Main {
    static int H;
    static int W;
    static int N;
    static int[][] stickers;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        N = Integer.parseInt(br.readLine());

        stickers = new int[N][2];

        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());
        }

        int sum = 0; // 넓이 합
        int max = 0; // 최대 넓이
        for(int i=0; i<N-1; i++) {
            for(int j=i+1; j<N; j++) {
                if(stickers[i][0] + stickers[j][0] <= H && Math.max(stickers[i][1], stickers[j][1]) <= W ||
                        stickers[i][0] + stickers[j][0] <= W && Math.max(stickers[i][1], stickers[j][1]) <= H) {
                    sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
                }
                else if(stickers[i][0] + stickers[j][1] <= H && Math.max(stickers[i][1], stickers[j][0]) <= W ||
                        stickers[i][0] + stickers[j][1] <= W && Math.max(stickers[i][1], stickers[j][0]) <= H) {
                    sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
                }
                else if(stickers[i][1] + stickers[j][0] <= H && Math.max(stickers[i][0], stickers[j][1]) <= W ||
                        stickers[i][1] + stickers[j][0] <= W && Math.max(stickers[i][0], stickers[j][1]) <= H) {
                    sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
                }
                else if(stickers[i][1] + stickers[j][1] <= H && Math.max(stickers[i][0], stickers[j][0]) <= W ||
                        stickers[i][1] + stickers[j][1] <= W && Math.max(stickers[i][0], stickers[j][0]) <= H) {
                    sum = stickers[i][0] * stickers[i][1] + stickers[j][0] * stickers[j][1];
                }
                if(max < sum) max = sum;
            }
        }
        bw.write(max + "");
        bw.flush();
        bw.close();
        br.close();
    }
}

코드 자체는 간단한데 문제를 이해하는 게 조금 어려웠던 것 같다.
스티커를 90도로 회전이 가능하기 때문에 모든 경우의 수를 다 조건문에 넣어주면 끝이다..

너무 노가다 문제 같다.. ㅎㅎ

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