문제 출처 : https://www.acmicpc.net/problem/1780

문제 파악

색종이 만들기, 쿼드 트리 문제에 이어 세번째 분할 정복 문제이다.
그 전 문제들은 2등분씩하여 분할하는 문제였다면 이 문제는 3등분해야 한다.

그 전 문제는 half = size // 2 해주고
divide 함수를 2*2 4번 호출해줬다면

이 문제는 3등분을 해주어야 하기에 여러 방법들이 있겠지만 나는 단순히

    one_third = size//3
    two_thirds = (size*2)//3

해준 뒤

divide 함수를 9번 호출하여 문제를 풀었다.

    divide(x,y,one_third)
    divide(x,y+ one_third, one_third)
    divide(x,y+ two_thirds, one_third)
    
    divide(x + one_third, y, one_third)
    divide(x + one_third, y + one_third, one_third)
    divide(x + one_third, y + two_thirds, one_third)

    divide(x + two_thirds, y, one_third)
    divide(x + two_thirds, y + one_third, one_third)
    divide(x + two_thirds, y + two_thirds, one_third)

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())

paper = []

for _ in range(N):
    paper.append(list(map(int,input().split())))

minus = 0 
zero = 0 
plus = 0

def divide(x, y, size):
    global minus, zero, plus
    base = paper[x][y]
    all_same = True

    for i in range(x, x+size):
        for j in range(y,y+size):
            if paper[i][j] != base:
                all_same = False
                break
        if not all_same: 
            break

    if all_same:
        if base == -1 :
            minus += 1
        elif base == 0:
            zero += 1
        else: 
            plus += 1
        return
    
    one_third = size//3
    two_thirds = (size*2)//3

    divide(x,y,one_third)
    divide(x,y+ one_third, one_third)
    divide(x,y+ two_thirds, one_third)
    
    divide(x + one_third, y, one_third)
    divide(x + one_third, y + one_third, one_third)
    divide(x + one_third, y + two_thirds, one_third)

    divide(x + two_thirds, y, one_third)
    divide(x + two_thirds, y + one_third, one_third)
    divide(x + two_thirds, y + two_thirds, one_third)

divide(0,0,N)

print(minus)
print(zero)
print(plus)

조금은 투박한 divide 9번 호출
3x3 까진 어떻게 됐지만 4x4 , 5x5 는 저렇게 해선 안될 것 같아
반복문 방법을 찾아 보았다.

one_third = size // 3

for dx in range(3):
    for dy in range(3):
        divide(x + dx * one_third, y + dy * one_third, one_third)

반복은 반복문으로 처리하자.

4분할 했어야 했다면 반복문을 떠올렸으려나?