1. Problem 📃

📚 ソース-2630-色紙の作成
問題の説明
下図1に示すように、正方形の格子からなる正方形紙が複数あり、各正方形は白または青に塗られている.与えられた紙を一定の規則に従って様々な大きさの正方形の白色または青色の紙に切る.

全紙サイズN×N(N=2 k,kは1以上7以下の自然数)の場合、切り紙のルールは以下の通りです.
用紙全体に同じ色が塗られていない場合は、<図2>のI,II,III,IVのように、中央部分を横方向と縦方向にカットしてください.× n/2は色紙に分かれている.分割された用紙I,II,III,IVについては,前のようにすべて同じ色を塗らなければ,同じ方法で同じ大きさの4つのカラー紙に分けられる.この過程を繰り返して、紙を全部白や青に塗ったり、正方形の格子になったりして、これ以上裁断できないまで繰り返します.
上記のルールに従って裁断する場合、『図3』は『図1』の用紙が1回目に分割された状態を示し、『図4』は2回目に分割された状態を示し、『図5』は最終的に作られた9枚の異なる大きさの白い用紙と7枚の青い紙を示した.

所定の用紙の長さNと各正方形のセルの色(白または青)を入力すると、カットされた白と青の用紙の個数を計算するプログラムを作成します.
入力
1行目は紙全体の片側長Nがある.Nは、2、4、8、16、32、64、128のうちの1つである.色紙の各横線の正方形の格子の色は、上から2行目から最後の行まで順番に変わります.白い格子は0で、青い格子は1で、数字の間にスペースがあります.
しゅつりょく
1行目はカットされた白い紙の個数、2行目は青い紙の個数を出力します.
I/O例
入力例出力811 0 0 0 0 0 1 11 1 0 0 0 0 0 1 10 0 1 10 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 197

2. Logic 👨‍🏫

いくつかの問題を解いたが,今では問題がどんなタイプなのかよく知っているようだ.この問題は典型的な分割征服、回帰問題である.だから解の形も悪くないから先に見てみよう
1つの数字でなければ、rowおよびcolは、1/2배に分割されて解決される.
この問題は2중 for문を用いて再帰的に解いたが,もう1つの方法は2중 for문を用いずに1, 2, 3, 4분면をそれぞれ呼び出して解決することである.
次のコードにコメントを追加します.

3. Code 💻

1.私が解いたパスワード😁

def check(row, col, n):
    global white, blue

    v = paper[row][col] # 값을 비교할 대상

    for i in range(row, row+n): # 시작점부터 n만큼의 길이만큼
        for j in range(col, col+n): # 시작점부터 n만큼의 길이만큼
            if v != paper[i][j]: # 만약 값이 다르다면 쪼개야 됨
                for k in range(2): # 이번 문제에서 1/2로 분할한다고 얘기했으니 row, col 각각 2로 나눠 대입
                    for l in range(2):
                        check(row + k * n//2, col + l * n//2, n//2)
                		# 총 4번 들어가게 되는데
                        # k = 0, l = 0 -> 1사분면
                        # k = 0, l = 1 -> 2사분면
                        # k = 1, l = 0 -> 3사분면
                        # k = 1, l = 1 -> 4사분면
                return
	# 만약 위의 조건을 통과했다면 여기까지 도달했을 것이다.
    # 모든 값이 일치한다는 말과 같으니 그 값에 따라 cnt를 증가시켜준다.
    if v == 0:
        white += 1
    elif v == 1:
        blue += 1

N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
white = 0
blue = 0

check(0, 0, N)
print(white)
print(blue)

参考資料📩
baekjoon 1992. 四叉木(分割征服)
baekjoon 1780. 用紙数（征服分割）