[백준] 2630번 파이썬 _ 색종이 만들기

www.acmicpc.net/problem/2630

2630번: 색종이 만들기

문제유형 : 분할정복, 재귀

 

문제풀이 :

• 아이디어 생각 자체는 어렵지 않은데 구현에서 먼가 꼬여서 생각보다 오래품
• 주어진 종이크기를 4등분하는함수 / 주어진종이가 모두 0인가(흰색정사각형인가)를 판단하는 함수 / 반대로 파랑인지 확인함수
• 이렇게 3개의 함수를 구현하고 풀었다

정답코드

import sys
input = sys.stdin.readline

n = int(input()) #종이 한변의 길이

paper = []
for _ in range(n):
    paper.append(list(map(int, input().split())))

def divide(paper): #주어진 종이크기를 4등분하는 함수
    s_1 = []
    s_2 = []
    s_3 = []
    s_4 = []
    n = len(paper)
    for i in range(0, n // 2):
        s_1.append(paper[i][:n // 2])
        s_2.append(paper[i][n // 2:])
    for i in range(n // 2, n):
        s_3.append(paper[i][:n // 2])
        s_4.append(paper[i][n // 2:])
    return s_1, s_2, s_3, s_4

blue = 0
white = 0

def check_all_1(paper): #현재 종이가 전부다 1인지 확인하는 함수
    for line in paper:
        for i in line:
            if i==0:
                return False
    global blue
    blue += 1
    return True


def check_all_0(paper): #현재 종이가 전부다 0인지 확인하는 함수
    for line in paper:
        for i in line:
            if i==1:
                return False
    global white
    white += 1
    return True

def count(paper, n):
    global white, blue

    if check_all_0(paper) or check_all_1(paper):  # 현재종이가 하나의 색이 아니므로 잘라야함
        return
    else:
        if n>=2:
            for i in divide(paper):
                count(i, len(i))

count(paper,n)
print(white)
print(blue)