색종이를 곱게 접어서 (백준 2630:색종이 만들기)

2630번: 색종이 만들기 (acmicpc.net)

2630번: 색종이 만들기

딱 봐도 Z랑 비슷하지 않는가?

배열 안의 1을 카운트해서 1의 갯수가 N x N이 아닌경우, 4분할을 하여 다시 1을 카운트 해보고 아니면 다시 4분할 하는 식으로 가자.

 

우선 입력값을 받고, 재귀함수의 기본꼴을 만들자.

일단 해당 색종이의 현재 좌표를 알아야하기 때문에 x, y를 넣어준다.

 

 

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

def devide(N, x, y):
    if sum(paper) == N * N:
        return N * N
    else:
        devide(N/2)

이제 여기에 나눌 때, 정보를 넘길 수 있도록 덧붙여주자.

다행히, 4분할의 어느 한쪽이 가득차있어도 다른쪽이 그렇지 않다면 4분할을 진행해야한다.

Z때와 똑같이 Z방향으로 0,1,2,3사분면이라고 하자.

기준좌표는 제일 오른쪽 밑이다. (초기 기준좌표는 (N,N))

 

그리고 나뉘어졌을 때, 네모판 안의 1의 갯수를 세주자.

만약 1의 갯수가 N*N이면 더 나누지 않고 blue_count (파랑색 색종이 갯수) 를 1더해주고

1의 갯수가 0이면 white_count(흰색 색종이 갯수)를 1 더해준다.

    for i in range(x-N, x):
        for j in range(y-N, y):
            if paper[i][j] == 1:
                sum_one += 1


    
    if sum_one == N * N: 
        blue_count += 1
        return

    elif sum_one == 0:
        white_count += 1
        return

그리고 만약 둘다 해당되지 않는다면, 다시 4분할 해서 재귀함수로 들어간다.

    else:
        devide(N//2, x-N//2, y-N//2)
        devide(N//2, x-N//2, y)
        devide(N//2, x, y-N//2)
        devide(N//2, x, y)
        return 

 

전체 코드는 다음과 같다.

import sys

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

def devide(N, x, y):
    global blue_count, white_count
    sum_one = 0


    for i in range(x-N, x):
        for j in range(y-N, y):
            if paper[i][j] == 1:
                sum_one += 1


    
    if sum_one == N * N: 
        blue_count += 1
        return

    elif sum_one == 0:
        white_count += 1
        return
    

    else:
        devide(N//2, x-N//2, y-N//2)
        devide(N//2, x-N//2, y)
        devide(N//2, x, y-N//2)
        devide(N//2, x, y)
        return 

devide(N, x, y)
print(white_count)
print(blue_count)




    

 

간단히 말했지만, 사실 N이랑 x랑 y가 헷갈려서 생각보다 시간을 많이 소모했다.

함수를 짜고 실행하기 전에 각 요소를 정확히 파악하는 훈련이 아직 덜된 것 같다. ㅜㅡㅜ