Baekjoon 2630번 색종이 만들기

문제

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

걸린 시간

01 : 35 : 52

풀이

Python3

def cut(paper):
    # 한 변의 길이
    side = len(paper)    

    b = blue = w = white = count = 0

    piece = paper[0][0]

    # 1x1 조각일 때
    if side == 1:
        if piece == '0':
            white += 1
        else:
            blue += 1
        return white, blue 

    # 조각이 모두 같은 색일 때
    for row in range(0, side):
        for col in range(0, side):
            if piece == paper[row][col]:
                count += 1

    if count == side**2:
        if piece == '0':
            white += 1
        else:
            blue += 1
        return white, blue

    # 4번의 순환 호출
    for i in range(0, side, side//2):
        for j in range(0, side, side//2):
            cut_paper = []
            for row in range(i, i+side//2):
                tmp = []
                for col in range(j, j+side//2):
                    tmp.append(paper[row][col])
                cut_paper.append(tmp)
            w, b = cut(cut_paper)
            white += w
            blue += b

    return white, blue        

if __name__ == "__main__":
    # 한 변의 길이
    N = int(input())
    paper = [input().split() for i in range(0, N)]    

    white, blue = cut(paper)

    print(white)
    print(blue)

색종이를 4등분할 때 마다 종이의 크기는 1/4 로 줄어들게 된다. 문제의 크기가 점점 작아지므로 순환 구조를 사용하는것이 바람직하다.