[BOJ 1992] 쿼드트리

1) 문제 링크

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

2) 접근

1780과 상당히 유사한 문제다. isSame 함수나 인수로 level 변수 넣는 거 많이 갖다 썼다. 차이점이 있다면 자료형이 문자라는 점?

3) 풀이

#include <iostream>
using namespace std;

int N;
char arr[64][64];

char isSame(int sy, int sx, int ey, int ex){
    char cr = arr[sy][sx];

    for(int i=sy; i<=ey; ++i){
        for(int j=sx; j<=ex; ++j){
            if(cr != arr[i][j]) { return -1; }
        }
    }
    return cr;
}

void solve(int y, int x, int level){
    if(level > 1){
        char kind = isSame(y, x, y+level-1, x+level-1);
        if(kind != -1){
            cout << kind;
            return;
        }
    }
    else{
        cout << arr[y][x];
        return;
    }

    cout << "(";
    solve(y, x, level/2);
    solve(y, x+level/2, level/2);
    solve(y+level/2, x, level/2);
    solve(y+level/2, x+level/2, level/2);
    cout << ")";

    return;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

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

    solve(0, 0, N);

    return 0;
}

시간 복잡도는 $O(NlogN)$
+이 문제 풀고 실1 승급함. 좀만 더 하면 골드!!

(2021-08-12) 지금은 골2이긴 한데… 이때랑 실력은 별 차이 없는 듯 ㅋㅋ

4) 피드백

나중에 할 거 있으면 추가할 예정.