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

1. 문제

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

1780번: 종이의 개수

2. 풀이과정

문제에서 주어진 규칙대로 해결하면 된다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

[코드설명]

check함수는 (y, x)를 좌측상단 꼭짓점으로 하고 한 변의 길이가 distance인 정사각형이

모두 같은 수로 이루어져 있는지 검사하고 모두 같은 수로 채워져 있을 경우, 해당 숫자를 리턴하며

이외의 경우에는 -2를 리턴한다.

 

solve함수는 check함수를 이용해 현재 정사각형이 모두 같은 수로 이루어져있는지 검사하고, 

모두 같은 수로 이루어져 있다면 해당 숫자 카운트를 증가시키고, 

그렇지 않다면 그 종이를 같은 크기의 9개의 종이로 자른다.

3. 코드

#include <iostream>
#include <vector>

using namespace std;
int cnt_one, cnt_m_one, cnt_zero;
vector<vector<int>> board;

int check(int y, int x, int distance) {
    int chk[3] = {0};
    if(distance == 1) return board[y][x];
    for(int i=y; i<y+distance; i++) {
        for(int j=x; j<x+distance; j++) chk[board[i][j]+1]++;
    }
    if(chk[0]==distance*distance) return -1;
    if(chk[1]==distance*distance) return 0;
    if(chk[2]==distance*distance) return 1;
    return -2;
}

void solve(int y, int x, int distance) {
    int ret = check(y, x, distance);
    if(ret!=-2) {
        if(ret == -1) cnt_m_one++;
        if(ret == 0) cnt_zero++;
        if(ret == 1) cnt_one++;
        return ;
    }
    for(int i=0; i<3; i++) {
        for(int j=0; j<3; j++) {
            int ny = y + (distance/3)*i;
            int nx = x + (distance/3)*j;
            solve(ny, nx, distance/3);
        }
    }
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    board.resize(n);
    for(int i=0; i<n; i++) {
        board[i].resize(n);
        for(int j=0; j<n; j++) cin >> board[i][j];
    }
    solve(0, 0, n);
    cout << cnt_m_one << "\n" << cnt_zero << "\n" << cnt_one;
    return 0;
}