[정글 week02] 백준 코테 종이 만들기 2630

종이 만들기

문제 정의

• n이 주어지면 n*n의 종이를 만든다.
• n*n 종이가 모두 1이라면 blue_count +1
• 0이라면 white_count +1

문제 풀이 방법

• 분할정복으로 접근 가능
• 처음 [row][col] 값을 가져와 다음 값을 비교 같다면 다음 값도 비교
• 다르다면 False 다음 실행

시간 복잡도

• 최악의 경우 : O(n^2)

알고리즘

• 분할정복 (영역 분할 기반의 쿼드 트리라고 한다.
  이 부분에 대해서는 나중에 찾아봐야 할 것 같다.)

N = int(input())
papers = [list(map(int, input().split())) for _ range(N)]

white_count = 0
blue_count = 0

def makingPaper(n, row, col):
    global white_count
    global blue_count
    first = papers[row][col]
    for i in range(row, row + n):
        for j in range(col, col + n):
            if first != papers[i][j]:
                break
        else:
            continue

        half = n // 2
        
        # 1사 분면
        makingPaper(half, row, col)
        # 2사 분면
        makingPaper(half, row, col+half)
        # 3사 분면
        makingPaper(half, row+half, col)
        # 4사 분면
        makingPaper(half, row+half, col+half)
        break
    else:
        if first == 1:
            blue_count += 1
        else:
            white_count += 1

makingPaper(N, 0, 0)
print(white_count)
print(blue_count)

for-else문

sum = 0
for i in range(5):
	 	sum += i
else:
	print(f"{sum} 출력")

for문이 정상적으로 실행됬다면 sum을 출력한다.
이처럼 break로 인해 interrupt 되지 않으면 else가 실행되고 그렇지 않다면 else를 지나친다.

기존에 풀어봤던 Z 문제랑 꽤나 유사한 문제.
하지만 Z를 어려워 했기에 잘 기억이 나지 않았다.

문제를 이해하고 정의 했는데 어떻게 구현을 시작해야 할지 막막했지만, 같은 조원의 힌트를 받아 문제를 해결할 수 있었다.

이 문제를 풀면서 느꼈던 것은 Z를 다시 풀어보자 ^___^
반복의 반복 내가 재귀가 되는 것 같구나...