[프로그래머스] 쿼드압축 후 개수 세기, 월간 코드 챌린지 시즌1, python

https://programmers.co.kr/learn/courses/30/lessons/68936?language=python3 

코딩테스트 연습 - 쿼드압축 후 개수 세기

def solution(arr):
    # 분할 정복
    answer = devideAndConquer(0,0,arr,len(arr))
    return answer

def devideAndConquer(r, c, arr, size):
    if len(arr) == 1:
        return [0, 1] if arr[r][c] else [1, 0]
    
    if check(r, c, arr, size):
        return [0, 1] if arr[r][c] else [1, 0]
    
    tmp1 = devideAndConquer(r, c, arr, size//2)
    tmp2 = devideAndConquer(r, c + size//2, arr, size//2)
    tmp3 = devideAndConquer(r + size//2, c, arr, size//2)
    tmp4 = devideAndConquer(r + size//2, c + size//2, arr, size//2)
    
    ret = [0, 0]
    ret[0] = tmp1[0] + tmp2[0] + tmp3[0] + tmp4[0]
    ret[1] = tmp1[1] + tmp2[1] + tmp3[1] + tmp4[1]
    return ret 
    

def check(r, c, arr, size):
    tmp = arr[r][c]
    for i in range(r, r + size):
        for j in range(c, c + size):
            if arr[i][j] != tmp:
                return False
    return True

level2 문제로 분할정복을 알면 쉽게 풀수 있는 문제이다.

분할정복은 top down방식인데 bottom up 방식으로도 풀 수 있는 문제이다.

 

다음은 분할정복으로 푸는 문제이다.

https://sinawi.tistory.com/308

[백준] 1992 쿼드트리 python

https://sinawi.tistory.com/293

[백준] 1629 곱셈 python

https://sinawi.tistory.com/335

[백준] 1780 종이의 개수, python

https://sinawi.tistory.com/279

[백준] 2630 색종이 만들기 python