[백준 / BOJ] C++ 1780 종이의 개수

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

1780번: 종이의 개수

문제

풀이

한변의 크기가 N인 정사각형을 입력받는다.

입력 받은 후 문제에서 제공되는 조건으로 종이를 자르거나 더해주거나 한다.

 

우선 전체 입력받을 종이 3^7 사이즈 2차원 배열과, 결과값을 저장할 result 배열을 선언한다.

다음 해당 종이의 행과 열의 숫자들을 비교하고, 모두 동일한 수인지 판단을 한다.

 

동일한 수가 아닐 경우, 입력받은 크기 N에 3을 나누어 해당 크기만큼 다시 동일한 사이즈 인지 비교를 한다.

이후 생성된 종이 내부의 값이 또 동일하지 않을경우 위와같이 또 나누어준다. 

 

즉, 분할정복을 이용하여 반복하면 됩니다. 

 

아래 코드를 보면 이해하기가 쉬우니 참고하자!

 

Code ( C++ )

#include <iostream>
#include <string.h>

using namespace std;

int N;
int _paper[2188][2188];
int result[3];

bool checkNum(int y, int x, int size)
{
    // 모두 같은 수 인지 아닌지 확인해야함.
    // 모두 같은 수일 경우
    int check = _paper[y][x];

    for(int i = 0; i < size; i++)
    {
        for(int j = 0; j < size; j++)
        {
            if(_paper[y + i][x + j] != check)
                return false;
        }
    }

    return true;
}
void checkPaper(int y, int x, int size)
{
    // 모든 수가 같다면 해당 종이 숫자 1 증가 
    if (checkNum(y, x, size))
    {
        int paperNum = _paper[y][x];
        result[paperNum + 1]++;
        return;
    }

    // 모든 수가 같지 않다면 3으로 나눠서 다시 확인
    int div = size / 3;

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            checkPaper(y + div * i, x + div * j, div);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    N = 0;
    cin >> N;

    // 종이배열 초기화
    memset(_paper, 0, sizeof(_paper));
    // 결과값 저장 배열 초기화
    memset(result, 0, sizeof(result));

    for (int y = 0; y < N; y++)
    {
        for(int x = 0; x < N; x++)
        {
            cin >> _paper[y][x];
        }
    }

    checkPaper(0,0,N);

    for(int i = 0; i < 3; i++)
        cout << result[i] << endl;

}