악곱 == 악성곱슬

분할 정복

---

해당 문제는 주어진 인풋이 2의 N승에, 그래프구조이다 → 분할정복으로 해결할 수 있는지 고민해보자.

이 문제는 일반적인 분할 정복과 크게 다를 것이 없는데, 나는 출력할 때 어떻게 해야 하나 고민했다. 그래서 재귀에 대해서 언제 괄호를 열고 닫아야 하나 고민을 했다. 서브문제를 풀기 전에 괄호를 열고 서브 문제가 다 해결되면 괄호를 닫는 방향으로 구현했다.

import sys

def is_same_num(l, r, t, b):
    color = graph[t][l]
    for i in range(t, b):
        for j in range(l, r):
            if graph[i][j] != color:
                return False
    return True

def divide(left, right, top, bottom):
    # 만약 한칸만 남은 상태면
    if left == right - 1 and top == bottom - 1:
        stack.append(graph[top][left])
        return
    # 모든 타일이 같다면
    if is_same_num(left, right, top, bottom):
        stack.append(graph[top][left])
        return
    # 더 분할해야 함
    mid_lr = (left + right) // 2
    mid_tb = (top + bottom) // 2
    stack.append('(')
    divide(left, mid_lr, top, mid_tb)
    divide(mid_lr, right, top, mid_tb)
    divide(left, mid_lr, mid_tb, bottom)
    divide(mid_lr, right, mid_tb, bottom)
    stack.append(')')

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    graph = list()
    for _ in range(N):
        graph.append(list(sys.stdin.readline().rstrip()))
    stack = list()
    divide(0, N, 0, N)
    answer = ''.join(stack)
    print(answer)