[C++] Boj 1780 종이의 개수

문제 링크

1780 종이의 개수

접근

재귀 함수라고 생각하고 너무 겁먹고 들어갔더니 처음엔 정말 안 풀렸다. 끙끙 앓다가 그냥 생각나는대로 로직을 추상적으로 짜서 도전해 보았다.

알고리즘

1. 현재 범위 내의 종이가 다 같은 종류의 종이인지 확인한다.

1-1. 만약 같은 종류라면 해당하는 종이의 카운트를 증가시킨다.

1-2. 만약 다른 종류라면 9등분해서 똑같이 1을 반복한다.

의사 코드

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> papers;

int N;
int paper[3];

void Solve(int x, int y, int n)
{
    if (/*만약 같은 종류의 종이라면*/)
    {
        paper[/*종이 인덱스*/]++;
        return;
    }

    // 만약 같은 종류의 종이가 아니라면
    // 종이 전체를 9등분 해서 다시 조사한다.
    int parts = n / 3; // 새로운 종이 범위
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            Solve(x + i * parts, y + j * parts, parts);
        }
    }
}


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

    // 종이 입력 받음
    cin >> N;

    papers = vector<vector<int>>(N, vector<int>(N, 0));

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> papers[i][j];
    
    Solve(0, 0, N);


    return 0;
}

코드

#include <iostream>
#include <vector>
using namespace std;

int papers[2200][2200];
int N;
int paper[3];

// 같은 종류의 종이인지 확인
bool CheckPaper(int x, int y, int n)
{
    int type = papers[x][y];
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++)
        {
            if (papers[i][j] != type)
                return false;
        }
    }

    return true;
}

void Solve(int x, int y, int n)
{
    if (CheckPaper(x, y, n))
    {
        paper[papers[x][y] + 1]++;
        return;
    }

    // 만약 같은 종류의 종이가 아니라면
    // 종이 전체를 9등분 해서 다시 조사한다.
    int parts = n / 3; // 새로운 범위
    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            Solve(x + i * parts, y + j * parts, parts);
        }
    }
}


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

    // 종이 입력 받음
    cin >> N;

    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> papers[i][j];
    
    Solve(0, 0, N);

    for (int i : paper)
        cout << i << '\n';

    return 0;
}

결과

 

재귀함수 진짜 싫다...