[BOJ] C++ 1780 종이의 개수 - 재귀, 헷갈리는 귀납적 사

1780번: 종이의 개수

 

예제

9
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
0 0 0 1 1 1 -1 -1 -1
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0
0 1 -1 0 1 -1 0 1 -1
0 -1 1 0 1 -1 0 1 -1
0 1 -1 1 0 -1 0 1 -1

ans:
10
12
11

---

문제의 규칙 자체가 분할 정복이다. 따라서 귀납적 사고를 통해 재귀 함수의 구조를 짜려했다. 귀납적 사고부터 해보자.

 

1. 1 * 1 크기의 종이는 당연히 셀 수 있다. 그러나 1 * 1 크기의 종이를 바로 base condition으로 설정하면 시간적으로도 비효율적이고 3 * 3 크기의 종이는 세지 않는 등의 문제가 있다. 따라서 base conditon은 따로 설정해줘야 한다.

2. n * n 크기의 종이를 셀 수 있다고 가정하면 3n * 3n 크기의 종이를 셀 수 있다. 왜냐하면 n * n 크기의 종이 9개를 붙인 것과 똑같기 때문이다.

 

이제 이를 바탕으로 재귀함수 구조를 짜보자.

 

1. 함수 정의 void func(int n, int a, int b) : n * n 크기의 종이를 (a, b)부터 센다.

2. base condition : check(int n, int a, int b) 함수를 사용한다. check() 함수는 n * n 크기의 종이가 모두 같으면 true를 리턴한다.

3. 재귀식

• n * n 개를 9 등분해서 func 함수를 돌리면 된다. 한 변은 당연히 3등분이다. k = n/3이라 하자.
• func(k, a + k * i, b + k * j) 
  • 0 <= (i, j) <= 2

/** 재귀 1780 종이의 개수 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int paper[2200][2200], N;
int ans[3] = {
    0,
};

bool check(int n, int a, int b)
{
    // n * n 종이의 숫자가 모두 같은지 정사각형 형태로 체크한다.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (paper[a][b] != paper[a + j][b + i])
                return false;
    return true;
}

void func(int n, int a, int b)
{
    // n * n 종이의 개수를 세는 함수이다.
    if (check(n, a, b))
    {
        ans[paper[a][b] + 1]++;
        return;
    }
    n = n / 3;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            func(n, a + i * n, b + j * n);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> paper[i][j];
    func(N, 0, 0);
    for (auto x : ans)
        cout << x << '\n';
}

지금까지 푼 문제는 귀납적 사고로 명확하게 재귀식, base condition이 나왔지만 이 문제는 조금 다른 느낌이다. 분할 정복임을 눈치채면 바로 재귀를 고려해 보자. 

---

이 문제와 거의 똑같은 문제도 몇 개 있다. 재귀를 연습하기 좋은 것들이다.

2630번: 색종이 만들기

종이의 개수 문제와 똑같은데 이등분이라는 점만 다르다.

색종이 자르기 정답 보기

/** 재귀 2630 색종이 자르기 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int paper[129][129], N;
int ans[2] = {
    0,
};

bool check(int n, int a, int b)
{
    // n * n 종이의 숫자가 모두 같은지 정사각형 형태로 체크한다.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (paper[a][b] != paper[a + j][b + i])
                return false;
    return true;
}

void func(int n, int a, int b)
{
    // n * n 종이의 개수를 세는 함수이다.
    if (check(n, a, b))
    {
        ans[paper[a][b]]++;
        return;
    }
    n = n / 2;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            func(n, a + i * n, b + j * n);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> paper[i][j];
    func(N, 0, 0);
    for (auto x : ans)
        cout << x << '\n';
}

 

1992번: 쿼드트리

이 문제는 괄호가 조금 헷갈릴 수 있다. 그럴땐 이 문제부터 풀어보자.

17478번: 재귀함수가 뭔가요?

재귀함수가 뭔가요? 정답 보기

/** 재귀 17478 재귀함수가 뭔가요? **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int k;

void chat_(int n)
{
    for (int i = 0; i < n; i++)
        cout << "____";
}

void chat(int n)
{
    chat_(n);
    cout << "\"재귀함수가 뭔가요?\"\n";
    if (n == k)
    {
        chat_(n);
        cout << "\"재귀함수는 자기 자신을 호출하는 함수라네\"\n";
        chat_(n);
        cout << "라고 답변하였지.\n";
        return;
    }
    chat_(n);
    cout << "\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n";
    chat_(n);
    cout << "마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n";
    chat_(n);
    cout << "그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n";

    chat(n + 1);

    chat_(n);
    cout << "라고 답변하였지.\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> k;
    cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
    chat(0);
}

쿼드트리 정답 보기

/** 재귀 1992 쿼드트리 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int video[64][64], N;

bool check(int n, int a, int b)
{
    // n * n 비디오의 숫자가 모두 같은지 정사각형 형태로 체크한다.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (video[a][b] != video[a + j][b + i])
                return false;
    return true;
}

void func(int n, int a, int b)
{
    if (check(n, a, b))
    {
        cout << video[a][b];
        return;
    }
    cout << "(";
    func(n / 2, a, b);
    func(n / 2, a, b + n / 2);
    func(n / 2, a + n / 2, b);
    func(n / 2, a + n / 2, b + n / 2);

    cout << ")";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; j < N; j++)
            video[i][j] = str[j] - '0';
    }
    func(N, 0, 0);
}