백준 - 2630번(재귀)

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

2630번: 색종이 만들기

 

import sys

n = int(sys.stdin.readline().strip())
arr = []
for i in range(n): #2차원 배열 형태로 처음 색종이 입력 받음
    arr.append(sys.stdin.readline().strip().split())

ans = []
b = [0]
w = [0]

def cut(arr):
    #색종이의 길이가 1보다 크면서 0,1 둘다 색종이 안에 있어야만 실행. 실행조건
    if len(arr[0]) > 1 and '0' in sum(arr,[]) and '1' in sum(arr,[]):
        a = len(arr[0]) // 2
        temp = [[],[],[],[]] # 다시 4등분할 색종이 생성

        for i in range(a):#열 a개를 넣기위해 반복문과 슬라이싱 사용
            temp[0].append(arr[i][:a])
            temp[1].append(arr[i][a:])
            temp[2].append(arr[i + a][:a])
            temp[3].append(arr[i + a][a:])

        for i in range(4):
          #4등분한 색종이 색상판별을 위해 재귀 호출
          cut(temp[i])

    #0,1 둘중 하나만 색종이에 존재하면 종료. 종료조건
    else:
        if arr[0][0] == '1':
            b[0] = b[0] + 1
        else:
            w[0] = w[0] + 1

cut(arr)

print(w[0])
print(b[0])

입력받은 색종이의 길이의 절반이 되도록 4등분으로 종이를 나눈다.

해당 종이 안에 0과 1이 같이 존재하면 다시 재귀를 호출해서 나눈다.

그렇지 않을경우 색상에 맞게 종이의 개수를 count 해준다.