문제

https://programmers.co.kr/learn/courses/30/lessons/68936

나의 코드 (답안참조)

"""
1. 아이디어

2. 시간복잡도

"""

def solution(arr): # 분할 정복 문제
    answer = [0, 0] # [0의 개수, 1의 개수]
    n = len(arr)
    
    def compress(x, y, l): # 압축해주는 함수
        num = arr[x][y]
        
        for i in range(x, x + l):
            for j in range(y, y + l):
                if arr[i][j] != num: # 배열 내부에 있는 수가 모두 같은 값이 아니라면 분할한다.
                    l = l // 2
                    compress(x, y, l)
                    compress(x, y+l, l)
                    compress(x+l, y, l)
                    compress(x+l, y+l, l)
                    return
                
        # 이 코드는 arr[i][j] == num 즉, 위의 반복문을 돌았을 때 특정 영역이 전부 다 같은 숫자일때만 실행된다.
        answer[num] += 1 # 배열 내부에 있는 수가 같은 값이라면 해당 숫자 개수를 +1 해준다.
    
    compress(0, 0, n)
    
    return answer
    

설명

분할정복 문제!

많이 쳐보고 그림 그려 봐야 하는 문제?

참고자료