'주어진 입력을 가지고 어떻게 출력이 도출되냐?'를 생각해봤을때 -> 만약 탐색범위내에 다른 값이 발견되면 시작점이 바뀌고 탐색 범위가 줄어들며 동일한 로직을 반복한다 -> 분할 정복 유형으로, 재귀함수나 stack을 이용해서 풀이한다 -> 나는 매개변수를 시작점, 탐색 사이즈로 잡고 stack을 이용해서 풀이할 것이다.

이 문제를 풀기위한 포인트가 존재한다.

(1) 매개변수 : 매 반복시마다 탐색의 시작점과 탐색범위가 바뀐다 -> 시작점(y,x)와 탐색 범위를 매개변수로 설정한다.
(2) 종료조건 : size가 1이면 시작점과 비교할 필요도없이 그냥 시작점의 값을 반환해주면된다
(3) 재호출: 어떨때 로직 반복이 필요할까? 구간 탐색했는데 시작점과 다른 값이 발견될경우 로직 반복이 필요하다 -> 재호출
(4) 괄호: 어떨때 괄호가 추가되어야할까? 구간 탐색했는데 시작점과 다른 값이 발견될경우 앞,뒤로 괄호를 추가해줘야한다 -> ret += '(' 로 괄호 추가해놓고 quard()를 재호출한다..마지막에 다시 ret += ')'로 괄호닫아준다.
(5) 탐색 순서 : 각 시작점마다 Z자로 탐색을 수행해야한다 -> 매개변수 size를 활용해 잘 조작해주기
(6) 다른 값 있는지 비교 : 시작점과 다른 값을 이중 for문을 통해 주어진 범위를 비교한다. (시작점을 비교의 기준값으로 잡으면 편하다)

1. 풀이

#include <bits/stdc++.h>
    
using namespace std;
char a[65][65];

string quard(int y, int x, int size) {
    if(size==1) return string(1,a[y][x]);
    string ret="";
    for(int i=y;i<y+size;i++) {
        for(int j=x;j<x+size;j++) {
             if(a[y][x] != a[i][j]) {
                 ret+="(";
                 ret+=quard(y,x,size/2);
                 ret+=quard(y,x+size/2, size/2);
                 ret+=quard(y+size/2,x, size/2);
                 ret+=quard(y+size/2,x+size/2, size/2);
                 ret+=")";
                 return ret;
             }
        }
    }
    return string(1, a[y][x]);   
}


int main() {
    int n;
    string s;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> s;
        for(int j=0;j<n;j++) {
            a[i][j] = s[j];
        }
    }
    string ret = quard(0,0,n);
    cout << ret;
    return 0;
}

2. 오답노트

(1) 분할 정복 유형을 처음 접했다

어떻게 풀어야할지, 그리고 재귀를 사용해야함 까지는 느낌이왔지만 이를 정확히 어떻게 구현해야할지 구체화하지 못했다. -> 각 재귀 호출마다 string을 유지하고, 그 string을 return 해주는 식으로 구현하는 방법을 잘 익혀둬야할 것 같다.

또한 분할 정복 유형의 코드 블럭을 잘 외워둬야겠다. 그게안되면 코드 구조, 느낌이라도 잘 외워둬야겠다.

(2) string(1,char)

string(1,char)는 char를 1번 반복한 string을 반환한다.

예를들어

string(1,'A'); // "A" 반환
string(2,'A'); // "AA" 반환

이런식이다.