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

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

2630번: 색종이 만들기

#백준 2630 색종이 만들기
import sys
input=sys.stdin.readline
white=0
blue=0
def all_same(p):
    global blue #파란색 종이의 개수를 담을 전역변수 생성
    global white #하얀색 종이의 개수를 담을 전역변수 생성
    len_p=len(p)
    s=0
    for i in range(len_p):
        s+=sum(p[i]) #각 요소의 합을 구함
    if s==(len_p*len_p): #모두 파란색이면
        blue+=1
        return 
    elif s==0: #모두 하얀색이면
        white+=1
        return 
    else: #그렇지 않으면
        rows=[val for val in range(0,len_p+1,len_p//2)] #행을 2분할
        columns=[val for val in range(0,len_p+1,len_p//2)] #열도 2분할
        for i in range(1,len(rows)):
            cut_rows=p[rows[i-1]:rows[i]] #행 자름
            for j in range(1,len(columns)):
                p_=list(zip(*cut_rows))[columns[j-1]:columns[j]] #열도 자름
                all_same(p_) #재귀로 반복


N=int(input())
paper=[]
for _ in range(N):
    paper.append(list(map(int,input().split())))
ans=all_same(paper)
print(white)
print(blue)

분할 정복에 익숙하지 않아서 그런지 되게 힘들었다. 더 연습해야지

 

더 깔끔하게 푸신 분의 풀이가 있어 첨부한다.

import sys

N = int(sys.stdin.readline())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] 

result = []

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


solution(0,0,N)
print(result.count(0))
print(result.count(1))

https://happylsm76.tistory.com/entry/%EB%B0%B1%EC%A4%80-2630%EB%B2%88%EC%83%89%EC%A2%85%EC%9D%B4-%EB%A7%8C%EB%93%A4%EA%B8%B0-with-Python <--링크