분할정복_백준 2630 색종이_파이썬

나눌 수 없을 때까지 나누어 각각 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

 

알고리즘 설계요령

1. Divide : 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.
2. Conquer : 나누어진 문제가 여전히 분할이 가능하면. 다시 Divide를 수행한다. 그렇지 않으면 문제를 푼다.
3. Combine : Conquer 한 문제들을 통합하여 원래 문제의 답을 얻는다

문제를 제대로 나누면 Conquer하는 것은 쉽기 때문에 Divide를 제대로 하는 것이 가장 중요하다.

분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아내릴 수 있다.

벡준 색종이 문제 

import sys
input = sys.stdin.readline

def list_sum(a:list):
    S=0
    for i in range(len(a)):
        S +=sum(a[i])
    return S

def divpaper(paper,end):
    paperA = []
    paperB = []
    paperC = []
    paperD = []
    S= list_sum(paper)

    if S==end**2:
        global Blue 
        Blue+=1
        return 
    elif S==0:
        global white
        white+=1
        return
    
    for i in range(end//2):
            paperA.append(paper[i][:end//2])  # 1사분면
            paperB.append(paper[i][end//2:])  # 2사분면
   
    for n in range(end//2,end):
            paperC.append(paper[n][:end//2])  # 3사분면
            paperD.append(paper[n][end//2:])  # 4사분면
    
    divpaper(paperA,len(paperA))
    divpaper(paperB,len(paperB))
    divpaper(paperC,len(paperC))
    divpaper(paperD,len(paperD))
    return

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


white = 0
Blue = 0
divpaper(paper,len(paper))

print(white)
print(Blue)