[PS] 백준 #16937. 두 스티커

문제 정보

• 난이도: 실버 IV
• 문제 주소: https://www.acmicpc.net/problem/16937
• 이 문제를 푼 이유: 알고리즘 스터디 - 브루트포스와 그리디

 

문제

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

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

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

 

나의 풀이

브루트포스로 모든 두 쌍의 스티커마다 붙일 수 있는지 여부를 확인해서 최댓값을 구하면 된다. 이때 붙일 수 있는지 여부를 확인하는걸 어떻게 할지 한참 고민했는데, 그림을 그려보니 두 스티커를 붙일 수 있는 형태는 최대 8가지임을 알 수 있었다. 좌상단에 1번째 스티커를 (그대로 / 회전)해서 붙여두고, 그 (오른쪽 / 아래쪽) 방향에 2번째 스티커를 (그대로 / 회전)해서 붙이는 경우만 존재한다. 따라서 해당 경우마다 스티커가 붙여진 영역의 width, height 를 구해서 전체 보드판보다 작거나 같은지를 확인해주었다.

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 브루트포스로 모든 두 쌍을 구해서 붙여보기
    int h, w, n; cin >> h >> w >> n;
    vector<pair<int, int>> vec(n);
    for (int i = 0; i < n; i++) {
        int r, c; cin >> r >> c;
        vec[i] = pair<int,int>(r, c);
    }
    int ans = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // 두 스티커 결정
            pair<int, int> p1 = vec[i], p2 = vec[j];
           // cout << p1.first << " , " << p1.second << " / " << p2.first << " , " << p2.second << endl;
            int h1 = p1.first, h2 = p2.first, w1 = p1.second, w2 = p2.second;
            
            // 회전 방향마다 테스트 -> 하나라도 되면 붙이기 가능
            bool stick = false;
            // 1. 1번 스티커 방향 그대로 붙였을 때
            // 1-1. 바로 오른쪽에 2번 스티커 그대로
            if (h1 + h2 <= h && max(w1, w2) <= w) stick = true;
            // 1-2. 바로 오른쪽에 2번 스티커 회전
            else if (h1 + w2 <= h && max(w1, h2) <= w) stick = true;
            // 1-3. 바로 아래쪽에 2번 스티커 그대로
            else if (max(h1, h2) <= h && w1 + w2 <= w) stick = true;
            // 1-4. 바로 아래쪽에 2번 스티커 회전
            else if (max(h1, w2) <= h && w1 + h2 <= w) stick = true;

            // 2. 1번 스티커 방향 회전 (w1, h1 회전)
            else if (w1 + h2 <= h && max(h1, w2) <= w) stick = true;
            else if (w1 + w2 <= h && max(h1, h2) <= w) stick = true;
            else if (max(w1, h2) <= h && h1 + w2 <= w) stick = true;
            else if (max(w1, w2) <= h && h1 + h2 <= w) stick = true;

            if (stick) {
                //cout << " Sticked!!\n";
                ans = max(ans, p1.first * p1.second + p2.first * p2.second);
            }
        }

    }
    cout << ans;

}