색종이 만들기

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

 

나의 풀이

import sys
input = sys.stdin.readline

n = int(input())
map_list = []
for _ in range(n):
    map_list.append(list(map(int, input().rstrip().split())))

result = [0,0]
def color_zip(a_idx, b_idx, n_lenth):
    now_color = map_list[a_idx][b_idx]
    for i in range(a_idx, a_idx+n_lenth):
        for j in range(b_idx, b_idx+n_lenth):
            if map_list[i][j] != now_color:
                color_zip(a_idx, b_idx, n_lenth//2)
                color_zip(a_idx, b_idx+(n_lenth//2), n_lenth//2)
                color_zip(a_idx+(n_lenth//2), b_idx, n_lenth//2)
                color_zip(a_idx+(n_lenth//2), b_idx+(n_lenth//2), n_lenth//2)
                return
    result[now_color] += 1
color_zip(0, 0, n)
for i in result:
    print(i)

 

시간 복잡도

모든 경우를 호출하는 경우 : ( 이차형 시간 복잡도 )
해당 알고리즘은 이차형 시간 복잡도 ( O(n**2) )