[boj] 2630번: 색종이 만들기

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

2630번: 색종이 만들기

 

 

 

1. 문제 설명 

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

 

 

 

2. 접근 방식 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

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

 

 

4. 분석

1. Time : n의 최대가 128이고, 2차원 배열이기때문에 (128 * 128) = 16384이고, 분할 정복의 TC는 O(NlogN)이기 때문에 주어진 1초안에 충분히 가능하다. 
2. Space :
3. 소요시간 : 1시간 
4. 제출 횟수 (무작정 제출하기 않기)  : 4회
5. 어려웠던 부분과 해결한 방법 : 비슷한 유형 많이 풀어보기
6. 실수가 줄어들었는가 ?