실버 II

💡문제 분석 요약

divide conquer 분할 정복

💡알고리즘 설계

우선 4개로 쪼갠 뒤, 쪼갠 부분의 시작을 나머지와 비교한다.

만약 다르다면 현재 탐색하는 부분을 4개로 쪼갠 뒤, 위를 반복한다.

💡코드

import sys
input= sys.stdin.readline
cut = [1,4,5,16,32,64,128]
n = int(input())
paper = []
for _ in range(n):
    paper.append(list(map(int,input().strip().split())))
    
def divide(x,y,n):
    global w,b
    color = paper[x][y]
    
    for i in range(x,x+n):
        for j in range(y,y+n):
            if color != paper[i][j]:
                divide(x,y,n//2)
                divide(x,y+n//2,n//2)
                divide(x+n//2,y,n//2)
                divide(x+n//2,y+n//2,n//2)
                return
    if color ==0:
        w+=1
    else:
        b+=1
        

w,b = 0,0
divide(0,0,n)

print(w,b, sep='\n')

💡시간복잡도

n log n

💡 기억할정보

divide conquer에 대해 좀 더 알자. 큰 문제를 작은 문제로 쪼개고, 쪼갠 것을 다시 더하면서 값을 계산하는 방식. 분할 정복은 dp와 달리 쪼갠 것이 독립적이다.
1. 분할: 문제를 작은 하위 문제로 분할.
2. 정복: 각 하위 문제는 재귀적으로 해결.
3. 결합: 하위 문제의 해결책을 결합하여 원래 문제를 해결.
## 분할 정복 알고리즘의 장점
1. 문제를 작은 부분으로 나누므로, 해결이 용이해진다.
2. 독립적인 부분 문제로 나누어져 병렬적으로 해결할 수 있다.
3. 데이터 구조가 배열이나 리스트로 구현이 가능하다.
## 분할 정복 알고리즘의 단점
1. 재귀 호출로 인한 오버헤드가 있다.
2. 스택 오버플로우가 일어날 수 있다.
3. 작은 부분으로 나누는 과정에서 많은 연산이 필요할 수 있다.