[ 백준 2858 ] 기숙사 바닥 (C++)

백준의 기숙사바닥(2858) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 타일의 갯수로 방의 가로와 세로 길이를 찾아내야 하는 문제이다. 방의 타일은 가장자리는 빨강색, 나머지는 갈색으로

   채워진다. 입력으로 빨강색 타일과 갈색타일의 갯수가 주어지는데, 우리는 이 값을 통해서 방의 넓이를 알아낼 수 있다.

   바로 "빨강색 타일의 갯수 + 갈색타일의 갯수 = 방의 넓이" 라는 것이다.

   이 후, 한변의 길이를 1부터 조건에 만족할 때 까지 계속해서 증가시키면서 방에 넓이가 충족되는지 확인해볼 것이다.

   근데 이 때, 조건이 하나 있어야 한다. 방의넓이 % 한변의 길이 = 0 이어야 한다는 것이다.

   예를 들어서 생각해보자. 방의 넓이가 12이다. 이 때, 한 변의 길이를 5로 탐색을 하는 것이 의미가 있을까??

   한 변의 길이가 5가 되는 순간, 다른 한 변의 길이가 어떤 값이 오더라도 절대 12가 될 수가 없다. 따라서 탐색을 할 때, 한변의

   길이를 계속해서 ++시키면서 탐색을 하되, 방의 넓이 % 한변의 길이 = 0 이라는 조건이 있어야 한다.

2) 그렇다면, 방의 넓이 % 한변의 길이 = 0 일 경우에는 어떻게 계산하는지 알아보자.

   위에서, 1부터 계속 ++ 시키면서 조건에 만족할 때 까지 반복한다고 했다. 그렇다면 한변의 길이가 A일때를 생각해보자.

   A일때, 다른 한변의 길이는 방의넓이/A(=B라고 하겠음) 가 될것이다.(두 개 곱하면 방의 넓이)

   이 두 변의 길이를 가지고, 실제로 타일의 갯수를 Count해보는 것이다.

   한 변의 길이가 A, 다른 한 변의 길이가 B인 직사각형의 모든 칸들을 탐색해보면서, 가장 자리에 있는 타일의 갯수를 Count하고,

   그게 아닌 타일의 갯수를 Count해서, 입력으로 주어진 빨강 타일의 갯수와 갈색 타일의 갯수가 일치하면,

   A와 B가 답이 되는 것이다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
using namespace std;
 
int Red, Brown;
int Room_Size;
bool Flag = false;
 
void Input()
{
    cin >> Red >> Brown;
    Room_Size = Red + Brown;
}
 
void Paint(int L, int W)
{
    int Tmp_R = 0;
    int Tmp_B = 0;
    for (int i = 0; i < W; i++)
    {
        for (int j = 0; j < L; j++)
        {
            if (i == 0 || j == 0 || i == W - 1 || j == L - 1) Tmp_R++;
            else Tmp_B++;
        }
    }
 
    if (Tmp_R == Red && Tmp_B == Brown)
    {
        Flag = true;
        return;
    }
}
 
void Solution()
{
    int Len = 1;
    while (1)
    {
        if (Room_Size % Len == 0)
        {
            int Tmp_L = Len;
            int Tmp_W = Room_Size / Len;
            Paint(Tmp_L, Tmp_W);
 
            if (Flag == true)
            {
                cout << Tmp_W << " " << Tmp_L << endl;
                return;
            }
        }
        Len++;
    }
}
 
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;
}