BOJ 1780 - 종이의 개수

whipbaek·2021년 9월 24일
0

BOJ

목록 보기
10/15

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

n*n의 색종이가 존재한다.
각 칸에는 -1,0,1의 값이 들어가있다.
(1) 값이 모두 같다면 종이를 사용한다.
(2) 값이 하나라도 다르다면 종이를 9개로 나누어 (1)과정을 다시 검사한다.
(3) 값이 -1,0,1인 색종이들의 각각 사용 가능한 개수를 출력한다.

Solution

분할정복의 대표적인 문제이다.
큰 문제를 작은 문제로 나누어서 해결할 수 있다.

9분할을 하기위해서는 식의 일반화가 필요하다.

만약 n이 9일시 값을 검사하고, 다르다면

(0, 0), (0, 3), (0, 6)
(3, 0), (3, 3), (3, 6)
(6, 0), (6, 3), (6, 6)

위와 같이 9분할을 할 수 있다.

이후에는 분할된 종이에서 같은 과정을 반복해준다.

(3, 3)에서 만약 분할해야 한다면

(3, 3), (3, 4), (3, 5)
(4, 3), (4, 4), (4, 5)
(5, 3), (5, 4), (5, 5)

와 같이 나뉘게 될 것이다.

첫번째로 호출하게 되는 부분은 분할되어진 종이의 가장 좌 상단 부분이다.
그곳으로 부터 n/3 의 크기만큼 검사를 하게 된다.
(n == 9 일 때 n/3 == 3, --> 3부터 5까지 3개의 값을 검사하게 됨)

Code

#include <bits/stdc++.h>
using namespace std;

int a[3000][3000];
int ans[3];

bool same(int x, int y, int n) {

    for (int i = x; i < x + n; i++) {
        for (int j = y; j < y + n; j++) {
            if (a[x][y] != a[i][j])
                return false;
        }
    }

    return true;
}

void solve(int x, int y, int n) {
    
    //숫자들이 모두 같다면
    if (same(x, y, n)) {
        ans[a[x][y] + 1] += 1;
        return;
    }

    //그렇지 않다면 9등분 해준다.
    else {
        int res = n / 3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                solve(x + i * res, y + j * res, res);
            }
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //종이의 숫자가 다르다면 9등분 해준다.
    //같을시에는 출력해준다.
  
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }

    solve(0, 0, n);

    for (int i = 0; i < 3; i++)
        cout << ans[i] << '\n';

    return 0;
}

solve 함수에 들어가는 인자가 중요한데,

solve(x + i * res, y + j * res, res);

이해가 잘 안갈시 위쪽에서 예시를 들었던 n==9일때의 과정을 따라가본다면 이해가 빠를것이다.


참고 : https://code.plus/course/43 , 분할 정복(연습)

profile
코딩 및 CS에 관하여 공부합니다.

0개의 댓글