- 오늘의 계획
- 프로그래머스/백준 사이트에서 알고리즘 문제 풀이(분할 정복)
-
오늘의 회고
- 분할 정복 문제 풀이 : 백준 2630번(색종이 만들기)
- 동계 모각코 때 풀이한 분할 정복 문제와 유사하였다.
- 색종이의 초기 위치인 0,0부터 시작하여 색종이의 모든 사분면을 판단하여 다른 색이 있다면 재귀를 사용해 사분할한 색종이를 다시 check하도록 하였고, 전부 흰색이거나 파란색인 경우에 색종이의 개수를 추가하였다.
-
코드 :
```python n = int(input()) paper = [list(map(int, input().split(" "))) for _ in range(n)] white = 0 blue = 0 def check(x, y, n): global blue, white validation = paper[x][y] for i in range(x, x + n): for j in range(y, y + n): if validation != paper[i][j]: check(x, y, int(n/2)) check(x + int(n/2), y, int(n/2)) check(x + int(n/2), y + int(n/2), int(n/2)) check(x, y + int(n/2), int(n/2)) return if validation == 0: # 전부 흰색 white += 1 return else: # 전부 파란색 blue += 1 return check(0, 0, n) print(white) print(blue) ```
- 분할 정복 문제 풀이 : 백준 2630번(색종이 만들기)