문제 1780 (C++) - 종이의 개수

문제 풀이

 

재귀를 이용한 분할 정복 알고리즘을 적용하면 쉽게 해결 가능하다.

 

 

종이에 적힌 숫자가 모두 같은 수로 되어 있지 않으면 9개의 종이로 잘라야 한다.

 

종이 한 변의 길이를 N, 왼쪽 위 꼭짓점 좌표를 x, y로 한다면 

 

왼쪽 위 꼭지점	한 변의 길이
x, y	N / 3
x + N / 3 , y	N / 3
x + 2 * (N / 3) , y	N / 3
x  , y + N / 3	N / 3
x + N / 3 , y + N / 3	N / 3
x + 2 * (N / 3) , y + N / 3	N / 3
x  , y + 2 * (N / 3)	N / 3
x + N / 3 , y + 2 * (N / 3)	N / 3
x + 2 * (N / 3) , y + 2 * (N / 3)	N / 3

 

인 9개의 종이로 나누어야 한다.

 

종이에 적혀있는 모든 숫자가 같은 경우 종이를 9개로 분할할 필요 없이

해당 숫자가 적혀있는 종이의 개수에 1을 더하면 된다.

 

 

 

코드

 

 

#include <iostream>
#include <string>
 
using namespace std;
 
#define MAX 2188
 
int arr[MAX][MAX];
 
// count[0] : -1 numbers , count[1] : 0 numbers , count[2] : 1 numbers
int count[3];
 
 
bool check(int x, int y, int n) {
 
    int first_num = arr[x][y];
 
    for (int i = x ; i < x + n ; i++ ) {
        for (int j = y ; j < y + n ; j++ ) {
            if ( first_num != arr[i][j] )
                return false;
        }
    }
 
    return true;
}
 
void division (int x, int y, int n ) {
 
 
    if ( check(x, y, n) ) {
        count[arr[x][y] + 1] += 1;
        return;
    }
 
 
    int d = n / 3;
    division(x , y , d);
    division(x + d , y , d);
    division(x + 2*d , y , d);
    division(x , y + d , d);
    division(x + d, y + d , d);
    division(x + 2*d, y + d , d);
    division(x , y + 2*d , d);
    division(x + d, y + 2*d , d);
    division(x + 2*d, y + 2*d , d);
 
}
 
 
 
int main(void) {
 
    int N;
    cin >> N;
 
    for (int i = 0; i < N ; i++ ) {
        for (int j = 0; j < N ; j++ )
            cin >> arr[i][j];
    }
 
    division(0 , 0 , N);
 
    cout << count[0] << endl;
    cout << count[1] << endl;
    cout << count[2] << endl;
 
    return 0;
}
 
 

 

 

결과

 

 

 

 

처음 분할 정복 문제를 접했을 때는 전혀 손을 못 댔지만

재귀 함수를 이용한 분할 정복법에 익숙해지니 매우 수월하게 풀 수 있었습니다.