[ 백준 ] 16937 / 두 스티커

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
150/228
post-thumbnail

# Appreciation

/*
 * Problem :: 16937 / 두 스티커
 *
 * Kind :: Math
 *
 * Insight
 * - max(N)=100
 *   이 중 두개만 놓으면 되니 O(100^2)
 *   놓을 수 있는지 검사는 가로, 세로 길이만 따지면 되니까 O(1) 쯤 되지 않을까?
 *   ^= 실제로 가짓수 계산해보니 O(8) 이다
 *   그렇다면, 시간 제한내에 충분히 풀 수 있을 것 같다
 *
 * - 놓는 방법은... 총 몇가지지?
 *   + 두 스티커 각각을 (r1, c1), (r2, c2) 라고 하자
 *     스티커 1은 H=r1, W=c1 이고 스티커 2는 H=r2, W=c2 이다
 *     # 일단, 두 스티커 모두 회전 안시키고 그냥 놓는 방법은
 *       ------------            ------------
 *       | A ||     |            |     || A |
 *       -----|  B  |            |  B  |-----
 *            |     |            |     |
 *            -------            -------
 *
 *       -------                 -----
 *       |     |                 | A |
 *       |  B  |                 -----
 *       |     |                 -------
 *       -------                 |     |
 *       -----                   |  B  |
 *       | A |                   |     |
 *       -----                   -------
 *
 *       가로로 붙이는 방법 2가지, 세로로 붙이는 방법 2가지해서
 *       4가지가 나온다
 *       -> 여기에 각각을 회전시킬 수도 있고
 *          0도 회전은 180도 회전과 일치 / 90도 회전은 270도 회전과 일치하니
 *          0도 회전 = '안회전', 90도 회전 = '회전'이라고 하면
 *          (스티커 1, 스티커 2) = (안회전, 안회전)
 *                             (안회전, 회전)
 *                             (회전, 안회전)
 *                             (회전, 회전)
 *          4*4 = 16 총 16가지가 나온다
 *
 * - 그런데 가로로 붙이는 방법에서 누가 왼쪽, 오른쪽에 있느냐는 중요치 않다
 *   두 스티커를 붙였을 때 max(c1, c2) <= W 이며 r1+r2 <= H 인것만 생각해주면 된다
 *   마찬가지로 세로로 붙이는 방법에서 누가 위쪽, 아래쪽에 있느냐는 중요치 않다
 *   두 스티커를 붙였을 때 max(r1, r2) <= H 이며 c1+c2 <= W 인것만 생각해주면 된다
 *
 * Point
 * - 놓을 수 있는지 없는지 판별할 때,
 *   '선택한 두 스티커를 놓을 수 있다' 는
 *   '회전 여부를 고려한 4가지 방법중 한 방법 이상에서 선택한 두 스티커를 놓을 수 있다' 이니
 *   적절히 함수를 선언하고 정의해서 코드가 중복되지 않도록 하는 것이 좋을 것 같다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
int H, W;

// Set up : Functions Declaration
bool isFeasible(int r1, int c1, int r2, int c2);
bool isPossible(int r1, int c1, int r2, int c2);

int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> H >> W;
    int N; cin >> N;
    int R[N], C[N];
    for (int i=0; i<N; i++) {
        cin >> R[i] >> C[i];
    }

    // Process
    int ans = 0;
    for (int i=0; i<N; i++) {
        for (int j=i+1; j<N; j++) {
            int r1 = R[i], c1 = C[i]; /* 스티커 1 */
            int r2 = R[j], c2 = C[j]; /* 스티커 2 */
            if (isPossible(r1, c1, r2, c2)) { /* 놓을 수 있으면 */
                ans = max(ans, r1*c1 + r2*c2); /* 답을 갱신 */
            }
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
bool isFeasible(int r1, int c1, int r2, int c2)
/* 주어진 두 스티커를 놓을 수 있으면 true 를 반환, 그 외 false 를 반환 */
/* 회전 여부가 결정된 상태 */
{
    if (r1+r2 <= H && max(c1,c2) <= W) return true;
    if (max(r1,r2) <= H && c1+c2 <= W) return true;
    return false;
}

bool isPossible(int r1, int c1, int r2, int c2)
/* 주어진 두 스티커를 놓을 수 있으면 true 를 반환, 그 외 false 를 반환 */
/* 회전 여부는 고려되지 않은 상태 */
{
    if (isFeasible(r1, c1, r2, c2)) return true; /* (안회전, 안회전) */
    if (isFeasible(c1, r1, r2, c2)) return true; /* (회전, 안회전) */
    if (isFeasible(r1, c1, c2, r2)) return true; /* (안회전, 회전) */
    if (isFeasible(c1, r1, c2, r2)) return true; /* (회전, 회전) */
    return false;
}
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글