문제

<예제>
8							9    하얀색 카드 수
1 1 0 0 0 0 1 1				7	 파란색 카드 수
1 1 0 0 0 0 1 1
0 0 0 0 1 1 0 0
0 0 0 0 1 1 0 0
1 0 0 0 1 1 1 1
0 1 0 0 1 1 1 1
0 0 1 1 1 1 1 1
0 0 1 1 1 1 1 1

나의 풀이

1. 2번째 줄부터 차례대로 받아 행렬을 s에 저장한다.
2. 행렬의 1의 개수와 0의 개수를 count
3. cnt == (N-f)^2이면 모두 같은 수로 이루어져 있으므로 멈춤
   아니라면 4구역으로 나눠서 재귀 함수 
4. 1로 이루어져 있으면 blue +1
   0으로 이루어져 있으면 white +1

def recs(s, f, N, ff, M):
    global blue, white
    cnt = 0
    cnt_1 = 0
    for i in range(f, N):            # 첫번째 범위
        for j in range(ff, M):       # 두번째 범위
            if s[i][j] == 0:
                cnt += 1
            else:
                cnt_1 += 1
    if cnt == (N - f) ** 2:          # 0과 1의 개수가 전체와 같다면
        white += 1
    elif cnt_1 == (N - f) ** 2:
        blue += 1
    else:                            # 아니라면 재귀
        recs(s, f, (N+f)//2, ff, (M+ff)//2)      # 2사분면    2 | 1    
        recs(s, f, (N+f)//2, (M+ff)//2, M)       # 1사분면    3 | 4
        recs(s, (N+f)//2, N, ff, (M+ff)//2)      # 3사분면
        recs(s, (N+f)//2, N, (M+ff)//2, M)       # 4사분면


N = int(input())
s = [list(map(int, input().split())) for _ in range(N)]  # 행렬 채우기
blue = 0
white = 0

recs(s, 0, N, 0, N)
print(white)
print(blue)

• 초반에 첫번째 범위와 두번째 범위의 변수명을 헷갈리게 줘서 범위선정에 시간이 걸렸다.
• 재귀의 활용은 확실히 깨닫고나니 어떻게해서든 문제는 풀어냈다.
• 간략한 풀이도 아니고 변수명과 범위설정도 무작정이라 더욱 좋은 풀이를 찾아봐야겠다.

다른 풀이

import sys

N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

result = []

def solution(x, y, N):
  color = paper[x][y]
  for i in range(x, x+N):
    for j in range(y, y+N):
      if color != paper[i][j]:
        solution(x, y, N//2)
        solution(x, y+N//2, N//2)
        solution(x+N//2, y, N//2)
        solution(x+N//2, y+N//2, N//2)
        return
  if color == 0 :
    result.append(0)
  else :
    result.append(1)


solution(0,0,N)
print(result.count(0))
print(result.count(1))


# 4x4 행렬을 가정하면              범위 (x, x+N) (y, y+N)
# sol(0, 0, 4) -> sol(0, 0, 2)     (0, 2)   (0, 2)
#              -> sol(0, 2, 2)     (0, 2)   (2, 4)
#              -> sol(2, 0, 2)     (2, 4)   (0, 2)
#              -> sol(2 ,2, 2)     (2, 4)   (2, 4)

• 처음 색을 구하고 그 색과 다르면 재귀를 실행시켰다
• 범위 변수를 잘 잡았다(정사각행렬임을 잘 사용)

2630번 색종이 만들기