[백준 2630번] 색종이 만들기 (파이썬/python)

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

2630번: 색종이 만들기

 

분할정복 문제중 아마 가장 유명한 문제가 아닐까..

프로그래머스에도 쿼드 압축 후 개수 세기 라는 똑같은 문제가 있다.

 

각 상황들을 2를 나눈 값으로 분할해가며

같은 색종이로 구성되어있는지 탐색하며

같은 색종이로 구성되어있다면 갯수를 늘려주는 방식을 사용하면 된다.

 

 

import sys
from math import ceil
 
input = sys.stdin.readline
li = []
# 0 ,1
answer = [0, 0]
 
 
def cnt(x, y, n):
    num = li[x][y]
    for _ in li[x:x + n]:
        for j in _[y:y + n]:
            if j != num:
                return -1
    return num
 
 
def divide(x, y, n):
    result = cnt(x, y, n)
    if result == -1:
        divide(x, y, n // 2)
        divide(x, y + n // 2, n // 2)
        divide(x + n // 2, y, n // 2)
        divide(x + n // 2, y + n // 2, n // 2)
        return
    else:
        if result == 1:
            answer[1] += 1
        else:
            answer[0] += 1
        return
 
 
t = int(input())
for i in range(t):
    li2 = list(map(int, input().split()))
    li.append(li2)
 
divide(0, 0, t)
print(answer[0], answer[1], sep='\n')