분할정복_색종이 만들기(2630)

문제

풀이

• 색종이의 맨 왼쪽 맨 위의 좌표 값과 이중for문으로 확인한 색종이 범위 내에 값이 다르면 4장으로 자른다.
• 또 맨 왼쪽 맨 위의 자표값과 색종이 범위 내의 값이 같은지 다른지 확인한다.
• 이 때 색종이는 N//2 로 계속 작아지므로 for문의 범위를 계속 줄여나가면서 재귀 함수에 넣는다.
• 이중 for문이 종료되었을 경우(즉 맨 왼쪽 맨 위의 값과 색종이 범위 내의 값이 모두 같을경우) 맨 왼쪽 맨 위의 값이 0인지 1인지에 따라 count 변수에 +1 한다

코드

import sys
sys.stdin = open("input.txt", "rt")

def input():
    return sys.stdin.readline().rstrip()


def cutPaper(x,y,N):
    global cnt0, cnt1

    ch = paper[x][y]
    for curX in range(x,x+N):
        for curY in range(y,y+N):
            if ch != paper[curX][curY]:
                cutPaper(x,y,N//2)
                cutPaper(x+N//2,y,N//2)
                cutPaper(x,y+N//2,N//2)
                cutPaper(x+N//2,y+N//2,N//2)
                return
    if ch == 0 : 
        cnt0 += 1
    else: 
        cnt1 += 1


if __name__ == "__main__":
    N = int(input())
    paper = [list(map(int, input().split())) for _ in range(N)]
    cnt0 = 0
    cnt1 = 0

    cutPaper(0,0,N)
    print(cnt0,cnt1)

배운것

• 분할정복
• for문 많이 돌려도 범위가 //2 씩 줄어듦으로 재귀로 해도 괜찮구나 !
• 배열.count(찾고자하는 값) 하면 배열 안의 찾고자 하는 값의 개수를 반환한다.