백준_두 스티커_16937

두 스티커

문제

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

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

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

입력

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

출력

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

예제 입력

2 2
2
1 2
2 1

예제 출력

4

Code

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const [H, W] = input[0].split(' ').map(Number);
const N = +input[1]; // 스티커 개수
const stickers = []; // 스티커 길이
for (let i = 2; i < N + 2; i += 1)
  stickers.push(input[i].split(' ').map(Number));

let area = 0; // 최대 넓이 값
for (let i = 0; i < N; i += 1) {
  const [r1, c1] = [stickers[i][0], stickers[i][1]]; // 첫 번째 스티커
  // 모눈종이(HXW) 안에 들어올 때만 수행
  if ((r1 <= H && c1 <= W) || (c1 <= H && r1 <= W)) {
    for (let j = i + 1; j < N; j += 1) {
      const [r2, c2] = [stickers[j][0], stickers[j][1]]; // 두 번째 스티커
      // 모눈종이(HXW) 안에 들어올 때만 수행
      if ((r2 <= H && c2 <= W) || (c2 <= H && r2 <= W)) {
        if (
          // 1. 회전 X(가로로 이어 붙일 때, 세로로 이어 붙일 때)
          (c1 + c2 <= W && r1 <= H && r2 <= H) ||
          (r1 + r2 <= H && c1 <= W && c2 <= W) ||
          // 2. 1번째꺼 회전(가로로 이어 붙일 때, 세로로 이어 붙일 때)
          (r1 + c2 <= W && c1 <= H && r2 <= H) ||
          (c1 + r2 <= H && r1 <= W && c2 <= W) ||
          // 3. 2번째꺼 회전(가로로 이어 붙일 때, 세로로 이어 붙일 때)
          (c1 + r2 <= W && r1 <= H && c2 <= H) ||
          (r1 + c2 <= H && c1 <= W && r2 <= W) ||
          // 4. 둘 다 회전(가로로 이어 붙일 때, 세로로 이어 붙일 때)
          (r1 + r2 <= W && c1 <= H && c2 <= H) ||
          (c1 + c2 <= H && r1 <= W && r2 <= W)
        ) {
          area = Math.max(area, r1 * c1 + r2 * c2); // 최대 넓이 값 갱신
        }
      }
    }
  }
}

console.log(area);

풀이 및 해설

• 스티커 2장을 붙였을 때의 최대 넓이 구하기
  1. 2장의 스티커를 이어붙였을 때(가로, 세로) 모눈종이 벗어나지 않으면 넓이 값 갱신 이때, 회전 가능하다는 것을 고려!(4개의 조건문 존재)
     • 회전 X, 첫번째꺼 90도 회전, 두번째꺼 90도 회전, 둘 다 회전