[Python] 2630번 색종이 만들기

문제

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

풀이과정

• 입력 한 변의 길이 N N x N 종이의 정보
  
• 출력 하얀색 종이의 개수, 파란색 종이의 개수
  
• 접근법

  1. 잘린 영역에 모든 색상이 같은지 판별한다.

     하얀색이면 하얀색 카운트, 파란색이면 파란색 카운트

  2. 아니라면 4개로 쪼개준다.

     재귀함수로 구현하기, 매개변수는 해당 영역의 시작점(가장 왼쪽 위)

1780번이랑 풀이가 비슷하다.

import sys
input = sys.stdin.readline

N = int(input())
m = [list(map(int, input().split())) for _ in range(N)]

blue = 0
white = 0

def check(x, y, n):
    global blue, white
    color = m[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if color != m[i][j]:  # 하나씩 검사하다가 다른 색이 있으면 잘라야한다.
                check(x, y, n//2)
                check(x, y+n//2, n//2)
                check(x+n//2, y, n//2)
                check(x+n//2, y+n//2, n//2)
                return
    if color == 1:
        blue += 1
    else:
        white += 1

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

나누어지는 좌표를 생각해서 구하면 쉽게 구할 수 있다.