BOJ 백준 2630번 색종이 만들기 | Python
문제 설명
🩶 실버 2
- 난이도 ★☆☆☆ - 분할정복
분할정복은 큰 문제를 작은 문제로 분할하여 해결하는 방법이다. 크기가 커지지만 않으면 굉장히 효율적인 방법으로, 시간복잡도는 O(NlogN)을 가진다. 그러나 재귀를 사용하기 때문에 크기가 커지면 메모리가 제한적이라는 단점이 있다.
이 문제는 많이 접하지 않았다면 풀이에 시간을 꽤나 소요했을 것이다.
📌 문제 풀이 큰 틀은 다음과 같다.
- 다른 색을 발견하면 색종이를 4개로 자르기
- 같은 색으로만 된 종이가 나온다면, 개수 추가
내 코드
import sys
input = sys.stdin.readline
N = int(input())
papers = []
for _ in range(N):
papers.append(list(map(int, input().split())))
white, blue = 0, 0
def solution(x, y, n):
global white, blue
color = papers[x][y]
for i in range(x, x+n):
for j in range(y, y+n):
if color != papers[i][j]:
# 잘라진 종이가 모두 같은 색이 아니라면 네 개로 자르기
solution(x, y, n//2)
solution(x + n//2, y, n//2)
solution(x + n//2, y + n//2, n//2)
solution(x, y + n//2, n//2)
return
# 모두 같은 색이면 더해주기
if color == 0:
white += 1
else:
blue += 1
solution(0, 0, N)
print(white)
print(blue)
💙 You need to log in to GitHub to write comments. 💙
If you can't see comments, please refresh page(F5).