[ 백준 16937 ] 두 스티커 (C++)

백준의 두 스티커(16937) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 스티커를 골라내는 방법과 회전하는 것을 어떻게 처리할 지에 대해서 알아본 후에, 스티커를 모눈종이에 붙이는 차례로

   알아보자.

   입력으로는 스티커의 갯수와 각 스티커의 가로, 세로 길이가 주어진다.

   하지만, 이 스티커들은 고정되어 있는 스티커가 아니라 회전시킬 수 있다. 회전시키게 되면 아마도 가로와 세로의 길이가

   바뀌게 될 것이다.

   본인은 입력과 동시에 스티커들의 가로와 세로길이를 Vector의 pair로써 저장해 주었다.

   그런데, 가로와 세로의 길이가 다를 경우에는 서로 값을 뒤집은 것도 함께 넣어주었다.

   예를 들면 다음과 같다. 가로의 길이가 1, 세로의 길이가 2인 스티커가 입력으로 주어진다면,

   Vector에 (1, 2)를 넣어주고, (2, 1)또한 넣어주었다. 하지만, 가로의 길이가 1이고 세로의 길이가 1과 같이 가로 = 세로인

   스티커에 대해서는 회전시키더라도 가로와 세로의 길이가 변하지 않기 때문에 하나의 값만 넣어주었다.

   이 후, 스티커를 2개를 뽑는 것은 조합 구현을 통해서 뽑아주었다.

   순서에 영향을 미치지 않기 때문에 순열이 아닌 조합을 사용하였다. 예를 들어서, 1번 스티커를 뽑고 2번 스티커를 뽑아서

   1 + 2번 스티커를 붙이는 것이나, 2번스티커를 뽑고 1번 스티커를 뽑아서 2 + 1번 스티커를 뽑아서 붙이는 것이나

   결과가 달라지지 않기 때문에 순서에 영향을 미치지 않는다고 판단할 수 있다.

  

2) 스티커를 뽑을 때 일반적인 조합 코드를 사용해도 되지만 본인과 같은 방법으로 스티커를 저장해 주었다면 주의해야 할

   점이 하나 있다.

   바로 같은 스티커를 2번 뽑는 경우이다.

   예를 들어서 설명해 보면 다음과 같은 상황이다.

   (가로의 길이, 세로의 길이) 가 (1, 3)인 스티커와 (2, 4)인 스티커 2개가 입력되었다고 가정해보자,.

   본인의 입력대로라면 벡터에 { 1, 3 } , { 3, 1} , { 2, 4 } , { 4 , 2 } 가 삽입되게 될 것이다.

   하지만 여기서 ! {1 , 3 } 과 { 3, 1 } 이렇게 2개의 스티커를 뽑는다고 생각해보자. 말이 안되는 상황이다.

   따라서 ! 위에서 설명하지는 않았지만 사실 벡터에서는 총 3개의 값을 관리하도록 만들어 주었다.

   바로, { { 가로길이, 세로길이 } , 스티커의 번호 } 이렇게 3개의 값을 관리해주었다.

   위의 예시로 예를 들면 벡터에 { { 3 , 1 } , 0 } , { { 1, 3 } , 0 } , { { 2, 4 } , 1 } , { { 4 , 2 } , 1 }

   이렇게 값이 들어가도록 설정해 준 것이다.

   위의 예시라면 "총 4개의 스티커 중 2개를 뽑는 조합" 을 구현하면 되는 식이고, Select[]배열을 통해서

   몇 개를 뽑았는지 체크만 해주면 되었지만, '스티커의 번호' 라는 변수 때문에 Select2[] 배열을 하나 더 만들어서

   관리해 주었다.

   Select[]배열은 입력되어 있는 전체 스티커의 갯수에서 x번째를 뽑았는지를 Check 하는 배열이고

   Select2[] 배열은 전체 스티커 중에서 x번 스티커를 뽑았는지를 Check 하는 배열로써 사용해 주었다.

   아마 코드를 참고한다면, 기존의 조합 코드와는 조금 다를 수 있지만 이해할 수 있을 것이다.

3) 이런식으로 스티커를 다 뽑았다고 가정해보자. 이제는 스티커가 모눈종이 안에 들어가는지만 판단해 주면 되는데

   가장 쉬운 방법은 직접 스티커를 붙여보는 것이다. 어떻게 ? 가장 왼쪽 위에서부터 뽑은 2개의 스티커를 차례대로 붙여보면

   되는 것이다. 겹치지 않게 Visit[][] 배열을 통해서 체크를 해주면서 붙이면 답은 도출해 낼 수 있을 것이다.

   하지만 ! 본인이 직접 해본 결과 이 방법을 사용하니 시간초과가 발생하게 되었다.

   사실, 스티커를 직접 붙여보지 않아도 2개의 스티커가 모눈종이 안에 들어가는지 안들어가는지는 확인할 수가 있다.

   그 방법에 대해서 알아보자.

   먼저 A와 B 스티커가 있다고 가정해보자. A와 B스티커를 붙이는 방법은 "2가지" 뿐이다.

   가로로 길게 붙이거나 세로로 길게 붙이거나 !

   2개를 띄어서 붙일 수도 있지 않나 ? 아니면 대각선 형태를 이루도록 붙일수도 있지 않나 ? 라고 생각할 수 있지만

   어차피 모눈종이 안에 스티커 2개를 넣어주기만 하면 된다. 굳이, 띄어서 붙이면서 경우까지 계산을 할 필요는 없다는

   이야기 이다.

   본인이 생각한 2가지 경우는 다음 그림과 같다.

   스티커를 이렇게 붙이는 것 2가지 경우 뿐이다.

   그럼, 먼저 가로로 길게 붙이는 왼쪽 그림과 같은 경우를 생각해보자.

   저 2개의 스티커가 모눈종이에 들어가기 위해서는 먼저 조건이 하나 필요하다.

   바로 "A의 가로길이 + B의 가로길이 <= 모눈종이의 가로길이" 라는 것이다. 만약 이 조건에 위배된다면 이 2개의

   스티커를 가로로 길게 붙이지는 못할 것이다.

   그렇다면 저 조건을 만족했다면 다음으로 고려해줘야 할 것은 무엇일까 ?? 바로 세로길이이다.

   왼쪽 그림을 보면 알 수 있다시피, 세로길이는 2개의 스티커의 길이를 더하는 개념이 아니다. 세로 길이가 더 긴 스티커의

   세로길이가 모눈종이의 가로길이 보다 짧기만 하면 스티커를 붙일 수 있다는 것을 의미한다.

   그렇다면 오른쪽 경우, 즉 세로로 길게 붙이는 경우를 생각해보자.

   저 2개의 스티커가 모눈종이에 들어가기 위해서는 "A의 세로길이 + B의 세로길이 <= 모눈종이의 세로길이"

   가 되어야 하고 이 조건을 만족했다면, 2개의 스티커 중 가로길이가 더 긴 스티커의 가로길이가 모눈종이의 가로길이보다

   짧기만 하면 들어갈 수 있다는 것을 알 수 있다.

  

   이런식으로 직접 붙여보지 않고 길이만으로도 충분히 파악할 수 있다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int H, W, N, Answer;
bool MAP[MAX][MAX];
bool Select[MAX];
bool Select2[MAX];
vector<pair<pair<int, int>, int>> V;
vector<pair<int, int>> Sticker;
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> H >> W >> N;
    for (int i = 0; i < N; i++)
    {
        int a, b; cin >> a >> b;
        if (a * b >= H * W) continue;
 
        if (a != b)
        {
            V.push_back(make_pair(make_pair(a, b), i));
            V.push_back(make_pair(make_pair(b, a), i));
        }
        else V.push_back(make_pair(make_pair(a, b), i));
    }
}
 
void DFS(int Idx, int Cnt)
{
    if (Cnt == 2)
    {
        int x = Sticker[0].first;
        int y = Sticker[0].second;
        int xx = Sticker[1].first;
        int yy = Sticker[1].second;
        int Size = (x*y) + (xx*yy);
 
        if (x + xx <= H)
        {
            int yyy = Bigger(y, yy);
            if (yyy <= W)
            {
                Answer = Bigger(Answer, Size);
            }
        }
        
        if (y + yy <= W)
        {
            int xxx = Bigger(x, xx);
            if (xxx <= H)
            {
                Answer = Bigger(Answer, Size);
            }
        }
        return;
    }
 
    for (int i = Idx; i < V.size(); i++)
    {
        if (Select[i] == true || Select2[V[i].second] == true) continue;
        Select[i] = true;
        Select2[V[i].second] = true;
        Sticker.push_back(make_pair(V[i].first.first, V[i].first.second));
        DFS(i, Cnt + 1);
        Sticker.pop_back();
        Select2[V[i].second] = false;
        Select[i] = false;
    }
}
 
void Solution()
{
    if (V.size() <= 1)
    {
        cout << 0 << endl;
        return;
    }
 
    DFS(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}