2630번: 색종이 만들기

김도형·2022년 10월 26일
0

출처 : 2630번: 색종이 만들기

Explanation:

종이의 크기가 N x N인 정사각형에서 각 칸에 1(파란색)과 0(하얀색)으로 칠해져있을 때 일정한 규칙에 따라 잘라서 자른 모든 면이 모두 같은 색이면 그 칸의 수를 반환하고, 모두 같은 색이 아니라면 똑같은 크기의 N/2 x N/2색종이로 조건을 만족할 때 까지 반복한다.


Algorithm:

Divide and conquer

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))

시간 복잡도

n의 최대가 128이고, 2차원 배열이기때문에 (128 * 128) = 16384이고, 분할 정복의 TC는 O(NlogN)이기 때문에 주어진 1초안에 충분히 가능하다.

profile
예비 FE 개발자

0개의 댓글