[백준 16937번] 두 스티커

문제 링크

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

 

문제 요약

모눈종이 안에 두 개의 스티커를 겹치지 않게 붙일 때, 그 넓이의 합의 최댓값을 구하는 문제이다.

 

문제 풀이

N의 크기가 작기 때문에 문제를 해결하기 위해 완전탐색을 사용할 수 있다. 따라서, 두 개의 스티커를 골라 모눈종이 안에 붙일 수 있는지 판단하는 함수를 작성하는 것이 이 문제를 해결하기 위한 핵심이다.

 

1. 첫 번째 스티커 붙이기

먼저, 한 개의 스티커를 모눈종이 안에 붙일 수 있는지 판단하는 함수인 isInside 함수를 작성한다. 이 함수는 왼쪽 사각형이 오른쪽 사각형을 포함할 수 있는지 판단한다. 왼쪽 사각형의 가로와 세로가 오른쪽 사각형의 가로와 세로보다 같거나 큰지 확인하는 것으로 구현할 수 있다.

bool isInside(int outer_width, int outer_height, int inner_width, int innder_height) {
    return outer_width >= inner_width && outer_height >= innder_height;
}

 

2. 두 번째 스티커 붙이기

첫 번째 스티커를 모눈종이 안에 붙일 수 있다면 이제 두 번째 스티커를 붙일 차례이다. 첫 번째 스티커를 붙일 때 왼쪽 위 꼭짓점에 맞춰서 붙이는 것이 두 번째 스티커를 붙일 공간을 최대한 확보하는 방법이다.

 

두 번째 스티커를 붙일 후보 공간들

첫 번째 스티커를 왼쪽 위에 붙이고 나면 두 번째 스티커를 붙일 수 있는 후보 공간들은 위 그림처럼 남은 아래 사각형 또는 오른쪽 사각형이 된다. 1번에서 구현한 isInside 함수를 이용하면 이를 구현할 수 있다.

bool canPlaceStickers(int s1_width, int s1_height, int s2_width, int s2_height) {
    // 첫 번째 스티커를 붙일 수 없는 경우
    if (!isInside(w, h, s1_width, s1_height)) {
        return false;
    }
    
    // 두 번째 스티커를 남은 아래 사각형에 붙일 수 있는 경우
    if (isInside(w, h - s1_height, s2_width, s2_height)) {
        return true;
    }
    
    // 두 번째 스티커를 남은 오른쪽 사각형에 붙일 수 있는 경우
    if (isInside(w - s1_width, h, s2_width, s2_height)) {
        return true;
    }
    
    // 두 번째 사각형을 붙이지 못하는 경우
    return false;
}

 

3. 스티커 회전 고려하기

마지막으로 스티커를 90도 회전시키는 것도 고려해야 한다. 이는 스티커의 가로와 세로를 서로 바꾸는 방식으로 구현할 수 있다. 두 개의 스티커를 회전시키는 경우의 수 조합을 만들어 고려하면 선택한 두 개의 스티커를 붙일 수 있는지 판단할 수 있다.

for (int i = 0 ; i < n ; ++i) {
    for (int j = i + 1 ; j < n ; ++j) {
        int R1[] = {R[i], C[i]};
        int C1[] = {C[i], R[i]};
        int R2[] = {R[j], C[j]};
        int C2[] = {C[j], R[j]};
        
        for (int k = 0 ; k < 2 ; ++k) {
            for (int l = 0 ; l < 2 ; ++l) {
                int r1 = R1[k], c1 = C1[k], r2 = R2[l], c2 = C2[l];
                
                if (canPlaceStickers(r1, c1, r2, c2)) {
                    ans = max(ans, r1 * c1 + r2 * c2);
                }
            }
        }
    }
}

 

소스 코드

#include <stdio.h>
#include <algorithm>

using namespace std;

int h, w, n, R[110], C[110];

bool isInside(int outer_width, int outer_height, int inner_width, int innder_height) {
    return outer_width >= inner_width && outer_height >= innder_height;
}

bool canPlaceStickers(int s1_width, int s1_height, int s2_width, int s2_height) {
    // 첫 번째 스티커를 붙일 수 없는 경우
    if (!isInside(w, h, s1_width, s1_height)) {
        return false;
    }
    
    // 두 번째 스티커를 남은 아래 사각형에 붙일 수 있는 경우
    if (isInside(w, h - s1_height, s2_width, s2_height)) {
        return true;
    }
    
    // 두 번째 스티커를 남은 오른쪽 사각형에 붙일 수 있는 경우 =
    if (isInside(w - s1_width, h, s2_width, s2_height)) {
        return true;
    }
    
    // 두 번째 사각형을 붙이지 못하는 경우
    return false;
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &h, &w, &n);
    
    for (int i = 0 ; i < n ; ++i) {
        scanf("%d%d", &R[i], &C[i]);
    }
    
    int ans = 0;
    
    for (int i = 0 ; i < n ; ++i) {
        for (int j = i + 1 ; j < n ; ++j) {
            int R1[] = {R[i], C[i]};
            int C1[] = {C[i], R[i]};
            int R2[] = {R[j], C[j]};
            int C2[] = {C[j], R[j]};

            for (int k = 0 ; k < 2 ; ++k) {
                for (int l = 0 ; l < 2 ; ++l) {
                    int r1 = R1[k], c1 = C1[k], r2 = R2[l], c2 = C2[l];

                    if (canPlaceStickers(r1, c1, r2, c2)) {
                        ans = max(ans, r1 * c1 + r2 * c2);
                    }
                }
            }
        }
    }
    
    printf("%d\n", ans);
}