[BOJ] 1780 종이의 개수

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

1780번: 종이의 개수

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

recursive + divide&conquer

 

---------------------------------------------------풀이----------------------------------------------------

 

종이의 맨 왼쪽위 좌표 (sx,sy), 맨 오른쪽아래 좌표 (ex, ey)를 저장하는 structure node를 만들어 사용하였다.

큐에 아직 완료되지 않은(한 가지 숫자로 이루어지지 않은/이루어졌는지 체크하지 않은) 종이 위치 node를 저장해 큐가 비어있을 때까지  cut_paper()를 반복한다.

 

cut_paper()에서는 큐의 front를 cur로 받아오고,

cur이 전부 같은 숫자로 이루어졌는지 find_number()를 사용해 저장한다.

find_number()는 같은 숫자로 이루어졌으면 그 숫자를, 아니면 999를 리턴한다.

cur이 전부 같은 숫자로 이루어진 것이 아니라면, 9개로 잘라 다시 큐에 저장한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int map[3000][3000] = {0, };

typedef struct{
    int sx, sy, ex, ey;
}node;

// 종이의 시작점, 끝점
int minus_one = 0, zero = 0, plus_one = 0;
queue<node> not_found;

int find_number(int sx, int sy, int ex, int ey){
    int num = map[sx][sy];
    for(int i = sx; i <= ex; i++){
        for(int j = sy; j <= ey; j++){
            if(map[i][j] != num){
                return 999;
            }
        }
    }
    return num;
}

void cut_paper(){
    node cur = not_found.front();
    // 전부 같은 숫자로 이루어졌다면 종료
    int num = find_number(cur.sx, cur.sy, cur.ex, cur.ey);
    if(num == -1){
        minus_one++;
    }
    else if(num == 0){
        zero++;
    }
    else if(num == 1){
        plus_one++;
    }
    // 9개의 조각으로 나누어 not_found에 삽입하기
    else{
        int size = (cur.ex - cur.sx + 1) / 3;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                node tmp;
                tmp.sx = cur.sx+i*size;
                tmp.sy = cur.sy+j*size;
                tmp.ex = cur.sx+i*size+size-1;
                tmp.ey = cur.sy+j*size+size-1;
                not_found.push(tmp);
            }
        }
    }
}

// 종이가 모두 같은 수로 되어 있다면 그대로 사용.
// 아니면 종이를 같은 크기의 종이 9개로 자르고 반복.
int main(void){
    FASTIO;
    int N;
    cin >> N;   // 3^K 형태.
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> map[i][j];
        }
    }

    node tmp;
    tmp.sx = 0; tmp.sy = 0; tmp.ex = N-1; tmp.ey = N-1;
    not_found.push(tmp);
    // not_found가 없어질 때까지 반복
    while(!not_found.empty()){
        cut_paper();
        not_found.pop();
    }

    cout << minus_one << "\n" << zero << "\n" << plus_one << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

제출하면 1%에서 out of bounds 오류가 계속 나서 무슨 문젠가 했더니

map[][]의 크기를 1000x1000으로 설정해 놓은게 문제였다.

3^7은 2187이므로 그 이상으로 해야하는데...네 자리 숫자길래 1000으로 설정해버린 것 같다. :(