[ SWEA 1812 ] 수정이의 타일 자르기 (C++)

SWExpertAcademy의 수정이의 타일 자르기(1812) 문제이다.

[ 문제풀이 ]

먼저, 주어진 TestCase를 가지고, 어떤 경우에 타일이 필요한지, 그리고 타일을 수직 - 수평 방향으로 자르게 되면 어떤 타일이 남게 되는지, 이에 따라서 정답이 어떻게 나오게 되는지부터 알아보자.

#1. 사각형 자르기

TestCase2번을 한번 확인해보자.

TestCase2번에서 수정이가 필요한 정사각형은 길이가 '4'인 2개의 정사각형이 필요하다.

그리고 가게에서는 길이가 '5'인 정사각형만 판다고 되어있다.

그럼 그림으로 한번 나타내보자.

.

위의 그림과 같이 필요한 정사각형은 한변의 길이가 4인 정사각형 2개가 필요하고, 가게에서 판매하는 정사각형은 길이가 5인 정사각형만 판매한다는 것이다.

( 지금부터는 단순하게 "길이가 x인 정사각형" 이라고 표현하겠습니다. 길이가 x인 정사각형이라는 것은, 한 변의 길이가 x인

  정사각형을 의미합니다. )

먼저, 타일을 채우기 위해서 "처음에 반드시 1번은 구매" 해야 한다. 왜냐하면 처음에 기본적으로 가지고 있는 타일은 없기 때문이다. 그럼 길이가 5인 정사각형을 먼저 첫 번째 길이가 4인 정사각형을 채운다고 생각해보자.

그럼, 문제에서 제시한 대로 정사각형은 반드시 수직 - 수평의 순서대로 잘라야 하니, 길이가 5인 정사각형을 길이가 4인 정사각형에 맞게 채우기 위해서 한번 잘라보자.

먼저 수직으로 자르면 다음과 같이 잘릴 것이다.

.

위와 같이 빨강색 점선을 기준으로 자르게 될 것이고, 오른쪽 그림과 같이 2개의 사각형으로 나눠질 것이다.

하지만, 아직 길이가 4인 정사각형을 만들지는 못했으므로, 위의 사각형을 한번 더 수평으로 잘라주어야 한다.

그럼 이렇게 자를 수 있다.

.

위와 같이 한번 더 자르게 되면, 길이가 4인 정사각형을 만들수가 있게 된다.

즉, 기존에 길이가 5인 정사각형이 다음과 같이 3개의 사각형으로 나눠지게 된 것이다.

위와 같이 3개의 사각형으로 나눠지게 된다.

그 중, 노랑색으로 색칠한, 즉 길이가 4인 사각형은 사용할 것이고, 결과적으로 색칠되지 않은 세로로 긴 사각형 하나와 가로로 긴 사각형 하나가 남게 될 것이다.

그럼, 여기서 남은 사각형들의 변의 길이에 대해서 이야기를 해보자.

먼저, 처음에 길이가 5인 사각형을 수직방향으로 잘랐을 때, 길이가 세로로 긴 사각형 하나가 떨어져 나왔다.

이 사각형의 세로길이 = 5 , 가로길이 = 1 이 된다.

그리고 그 이 후에 조각을 맞추기 위해서 수직방향으로 잘라내고 남은 사각형에서 수평방향으로 한번 더 잘랐더니,

가로로 긴 사각형이 떨어져 나왔다.

이 사각형의 세로길이 = 1 , 가로길이 = 4 가 된다.

즉, 5 x 5 사각형 = 4 x 4 사각형 + 5 x 1 사각형 + 1 x 4 사각형 으로 분리되어 진 것이다.

그럼 위의 Case에 맞춘 이야기말고 일반화된 이야기를 한번 해보자.

우리가 처음에 크기가 M x M인 정사각형을 가지고 있다고 가정해보자.

그리고 우리는 크기가 Len x Len 인 사각형에 맞추도록 사각형을 잘라야 하는 상황이다.

편의 상, Len < M 이라고 가정하겠다.

이런 경우 M x M 사각형을 Len x Len 사각형에 크기를 맞추게 자르고 나면, 우리가 가질 수 있는 남은 사각형은

M * M - Len 인 사각형과 , M - Len * Len 인 사각형을 가지게 되는 것이다.

위의 수식을 다시한번 우리가 진행했던 위의 예에서 진행해보자.

처음에 우리는 5 x 5 정사각형을 가지고 있었다. (M = 5)

우리는 4 x 4 정사각형에 맞게 잘라야 한다. (Len = 4)

자르고 나니, M * M - Len = 5 * 5 - 4 인 사각형, 즉 5 * 1의 사각형을 가지게 되었고,

M - Len * Len = 5 - 4 * 4 인 사각형, 즉 1 * 4 의 사각형을 가지게 되었다.

정리해보자. Len < M 일 경우, 크기에 맞게 정사각형을 자르고 난 후, 우리가 가질 수 있는 사각형은 다음과 같다.

1. 수직으로 자르게 될 경우

세로 = M , 가로 = M - Len 인 사각형을 가지게 된다.

2. 수평으로 자르게 될 경우

세로 = M - Len , 가로 = Len 인 사각형을 가지게 된다.

위와 같이 2가지 사각형을 가질 수 있게 된다.

#2. 정답 도출

먼저, 본인은 가장 먼저 내가 필요한 사각형들을 내림차순으로 정렬을 시켜 주었다.

왜냐하면, 그리디한 관점으로 봤을 때, 현재 내가 가지고 있는 사각형들을 가지고 필요한 사각형들을 채워야 하는데, 당연히 큰 사각형들을 채우는 것이 최소 구매가 될 것이기 떄문이다.

더 작은 사각형들을 채우고, 나중에 큰 사각형들을 채울 때에는 더 많은 구매가 필요할 수 있지만, 반대의 경우에는 그런 경우를 최소한으로 줄일 수 있기 때문이다.

본인은 3개의 변수를 관리하는 Vector를 이용해서, "현재 내가 가지고 있는 사각형" 을 관리해 주었다.

3개의 변수는 바로, [ 사각형의 세로 길이 , 사각형의 가로 길이 , 사용 여부 ] 이렇게 3가지를 관리해 주었다.

이미 사용한 사각형은 더 이상 사용할 수 없기 때문에 사용 여부 또한 변수로 관리해 주었다.

그럼, 현재 내가 가진 사각형으로 채우고자 하는 사각형을 채울 수 있는 경우는 언제일까 ??

바로, "내가 가진 사각형의 세로길이 >= 채우고자 하는 사각형의 세로길이 & 내가 가진 사각형의 가로길이 >= 채우고자 하는 사각형의 가로길이" 가 되는 것이다.

만약, 내가 가진 사각형의 길이 중 어느 하나라도 더 짧다면 해당 사각형을 잘라서 채우고자 하는 사각형을 만들 수는 없다.

채울 수 있다면, #1에서 진행했던 대로, 자르고 남은 사각형을 다시 "현재 내가 가지고 있는 사각형" 에 추가해 주면 된다.

이런식으로 진행을 하는데, 만약, "현재 내가 가지고 있는 사각형"들 중에서 현재 사각형을 채울 수 있다면, 더 이상의 구매가 필요하지 않은 것이고, 그게 아니라면 새롭게 구매를 해주어야 한다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
 
#define endl "\n"
#define MAX 510
using namespace std;
 
int N, M, Answer;
vector<int> Need_Tile;
vector<pair<pair<int, int>, bool>> Have_Tile;
 
void Initialize()
{
    Answer = 0;
    Need_Tile.clear();
    Have_Tile.clear();
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        int Len = 1;
        for (int j = 0; j < a; j++) Len <<= 1;
        Need_Tile.push_back(Len);
    }
}
 
bool Cmp(int A, int B) { return A > B ? true : false; }
 
void Solution()
{
    sort(Need_Tile.begin(), Need_Tile.end(), Cmp);
    Have_Tile.push_back(make_pair(make_pair(M, M), false));
    Answer++;
 
    for (int i = 0; i < Need_Tile.size(); i++)
    {
        int Need_Len = Need_Tile[i];
        bool Flag = false;
 
        for (int j = 0; j < Have_Tile.size(); j++)
        {
            if (Have_Tile[j].second == true) continue;    // 이미 사용한 타일은 사용못함.
            
            int Sero = Have_Tile[j].first.first;
            int Garo = Have_Tile[j].first.second;
            if (Sero >= Need_Len && Garo >= Need_Len)
            {
                Flag = true;
                Have_Tile[j].second = true;
                if(Garo > Need_Len)    Have_Tile.push_back(make_pair(make_pair(Sero, Garo - Need_Len), false));
                if(Sero > Need_Len) Have_Tile.push_back(make_pair(make_pair(Sero - Need_Len, Need_Len), false));
                break;
            }
        }
 
        if (Flag == false)
        {
            Answer++;
            if (M > Need_Len) Have_Tile.push_back(make_pair(make_pair(M, M - Need_Len), false));
            if (M > Need_Len) Have_Tile.push_back(make_pair(make_pair(M - Need_Len, Need_Len), false));
        }
    }    
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}