[재귀] 백준 1780: 종이의 개수

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

 

별다른 트릭이나 색다른 접근법 없이 정직하게 재귀함수만 작성하면 되는 문제이다.

 

base case 만 잘 지정해 주면 된다. 종이 크기가 한 장이면, 더 이상 나눌 필요가 없으므로 해당하는 숫자를 더해주고 재귀를 종료한다.

 

 if(size==1)
    {
        switch(paper[startRow][startCol])
        {
            case -1:
                minusOneNum++;
            break;
            case 0:
                zeroNum++;
            break;
            case 1:
                oneNum++;
            break;
        }

        return;
    }

 

size가 1보다 클 때는, 해당 종이만큼의 영역을 탐색하면서 숫자가 일치하는지 아닌지 여부만 판단해 준다. 일치하지 않을 경우, size를 3으로 나누어, 전체 종이를 9등분하여 다시 재귀함수를 호출한다.

int newSize = size/3;
for(int i=0;i<3;i++)
{
    for(int j=0;j<3;j++)
    {
        findPaperNum(paper, newSize, startRow+i*newSize, startCol+j*newSize);
    }
}

 

전체 코드 첨부하고 마친다.

#include <iostream>
#include <vector>

using namespace std;

int minusOneNum = 0;
int zeroNum = 0;
int oneNum = 0;

void findPaperNum(vector<vector<int>> &paper, int size, int startRow, int startCol)
{
    if(size==1)
    {
        switch(paper[startRow][startCol])
        {
            case -1:
                minusOneNum++;
            break;
            case 0:
                zeroNum++;
            break;
            case 1:
                oneNum++;
            break;
        }

        return;
    }

    bool isSameNumber = true;
    int number = paper[startRow][startCol];

    for(int r=startRow;r<startRow+size;r++)
    {
        if(!isSameNumber) break;
        for(int c=startCol;c<startCol+size;c++)
        {
            if(paper[r][c]!=number)
            {
                isSameNumber = false;
                break;
            }
        }
    }

    if(isSameNumber)
    {
        switch(number)
        {
            case -1:
                minusOneNum++;
            break;
            case 0:
                zeroNum++;
            break;
            case 1:
                oneNum++;
            break;
        }
        return;
    }
    else
    {
        int newSize = size/3;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                findPaperNum(paper, newSize, startRow+i*newSize, startCol+j*newSize);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;

    vector<vector<int>> paper(N, vector<int>(N, 0));

    int input;
    for(int r=0;r<N;r++)
    {
        for(int c=0;c<N;c++)
        {
            cin>>input;
            paper[r][c] = input;
        }
    }

    findPaperNum(paper, N, 0, 0);

    cout<<minusOneNum<<"\n"<<zeroNum<<"\n"<<oneNum;


}