[백준/Baekjoon] 1780 종이의 개수 C++ :: Divide and conquer

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

1780번: 종이의 개수

---

1. Logic

대표적인 분할정복의 예제인 것 같다.

N의 범위가 3^7이라고 했기 때문에 3^7=2187 넉넉잡아 배열의 크기를 2200으로 잡아줬다. 함수에 처음 들어가면 내가 지금 보고 있는 종이가 전부 같은 숫자로 이루어졌는지 확인 하고 하나라도 다르다면 다시 9등분으로 쪼개서 확인해 준다.

아래의 표는 코드의 주석과 대응되는 9등분 한 위치이다.

1	2	3
4	5	6
7	8	9

아래 코드를 보면 어떻게 돌아가는지 이해가 쉬울 것이다.

---

2. Code

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;


int input[2200][2200];

int zeroCnt = 0;
int minusCnt = 0;
int plusCnt = 0;

void solve(int y, int x, int size) {
    bool check = false;
    for(int i = y; i < y + size; i++) {
        for(int j = x; j < x + size; j++) {
            if(input[y][x] != input[i][j]) {
                check = true;
                break;
            }
        }
        if(check) break;
    }
    
    if(check) {
        //1, 2, 3
       solve(y, x, size / 3);
       solve(y, x + size / 3, size / 3);
       solve(y, x + 2*(size / 3), size/3);

        //4, 5, 6
       solve(y + size / 3, x, size/3);
       solve(y + size / 3, x + size / 3, size / 3);
       solve(y + size / 3, x + 2*(size / 3), size / 3);

        //7, 8, 9
       solve(y + 2*(size / 3), x, size / 3);
       solve(y + 2*(size / 3), x + size / 3, size / 3);
       solve(y + 2*(size / 3), x + 2*(size / 3), size / 3);
    }
    else {
        if(input[y][x] == 1) {
            plusCnt++;
        }
        else if(input[y][x] == 0) {
            zeroCnt++;
        }
        else if(input[y][x] == -1) {
            minusCnt++;
        }
    }
    
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> input[i][j];
        }
    }
    
    solve(0, 0, n);
    
    cout << minusCnt << "\n" << zeroCnt << "\n" << plusCnt;
}

---

3. Feedback

대표적인 분할정복의 예시

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐