1992 - 쿼드트리

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

1992번: 쿼드트리

 

- 분할정복법

 

import sys
input = sys.stdin.readline

def divide(arr):
    l = len(arr) // 2
    print('(', end='')
    for i in [0,l]:
        for j in [0,l]:
            quadtree([row[j:j+l] for row in arr[i:i+l]])
    print(')', end='')

def quadtree(matrix):
    l = len(matrix)
    value = [[matrix[0][0]] * l for _ in range(l)]

    if value == matrix:
        print(value[0][0], end='')
    else:
        divide(matrix)

n = int(input())
video = [list(map(int, input().rstrip())) for _ in range(n)]

quadtree(video)

 

쉬운 분할정복법 문제이다

 

1. 같은 수인지 확인

2-1. 같다면 그 수 출력

2-2. 다르면 분할

 

괄호 위치는 알잘딱깔센하게 넣어주면 됨