2630 - 색종이 만들기

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

2630번: 색종이 만들기

 

- 분할정복법

 

import sys
input = sys.stdin.readline

def divide(arr):
    l = len(arr) // 2
    
    divided_array = []
    for i in [0,l]:
        for j in [0,l]:
            divided_array.append([row[j:j+l] for row in arr[i:i+l]])
    
    
    for i in range(4):
        check(divided_array[i])
            

def check(paper):
    paper_l = len(paper)
    value = [[paper[0][0]] * paper_l for _ in range(paper_l)]

    if value == paper:
        cnt[paper[0][0]] += 1
    else:
        divide(paper)

n = int(input())

matrix = list()
for _ in range(n):
    matrix.append(list(map(int, input().split())))

cnt = [0, 0] # white, blue
check(matrix)

for i in cnt:
    print(i)

 

재귀를 이용한 분할정복법은 처음 풀어본 것 같다

 

분할정복법 중 일부인 이분탐색은 이제 익숙해졌는데, 이차원 리스트를 분할하며 재귀를 사용하는 분할정복법은 처음이라 많이 헷갈렸다

 

어디서 헷갈렸냐면, 분할>정복>통합 과정 중 분할...

 

정복이야 브루트 포스로 다 비교하면 되고, 통합이야 cnt 하나만 더해주면 되는 간단한 일인데.. 이차원 리스트를 분할해본 적이 없어서 좀 많이 고생했다

 

 

비슷한 문제 중에 종이의 개수라는 문제도 있는데, 이 문제도 분할을 못해서 포기했었다

 

시간 좀 오래걸렸지만, 그래도 풀어내서 기분이 좋다~ 이제 종이의 개수 문제도 쉽게 풀 수 있을 것 같다!!!!