[Python] BOJ 2630 : 색종이 만들기

요구사항

1. 시간 제한 1초 N**2 까지 ㅇㅋ
   1. N 은 대략10,000 정도 따라서 걱정
2. 메모리 제한
   1. 128MB - 128 * 10^6
3. 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만드려고 한다.
   1. 전체 종이가 모두 같은 색이 아니면 똑같은 크기로 N /2 등분 한다. (반복)

설계

1. 사용자로부터 N을 입력 받는다. 
2. 하얀색과 파란색을 입력 받는다. 리스트컨프리헨션으로 초기화
3. 결과값을 저장할 리스트 result 초기화
4. color= paper[x][y], 초기값은 0,0 이 들어간다.
5. 만약 color != paper[i][j] 이라면 분할한다.
   1.  1사분면
      1. x,y+N//2, N//2
   2. 2사분면
      1. x, y, N
   3. 3사분면
      1. x+N//2, N//2
   4. 4사분면
      1. x+N//2, Y+N//2, N//2
6. 같다면 더 이상 분할할 필요가 없으므로 return 해준다.
7. color == 0: 이라면 result.append(0)
8. 그 외 ( 1이라면 ) result.append(1)

헷갈렸던 부분

• for i in range() 의 범위를 어떻게 할까? 계속 범위는 달라질텐데
• 찾아보니 for i in range(x, x+N)을 해주면 된다고 한다.
• 그렇다면 x가 커질 수록 x+N 값도 커져 indexError 배열 초과가 일어나지 않을까?
• 하지만 설계를 보면 실제로 같지 않을 때, N값은 N//2 를 하므로 초과하지 않는다. 

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

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

def div(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]:
                div(x,y,N//2)
                div(x,y+N//2, N//2)
                div(x+N//2, y, N//2)
                div(x+N//2, y+N//2, N//2)
                return
    if color == 0:
        result.append(0)
    else:
        result.append(1)

div(0,0,N)

print(result.count(0))
print(result.count(1))