[백준] 2630 문제 in 파이썬

백준 2630 : 색종이 만들기

https://www.acmicpc.net/problem/2630

문제

풀이

분할정복법

• 이 문제는 분할정복법을 활용하는 문제이다. 따라서, 입력 받은 전체 종이부터 시작하여 네 부분으로 쪼개어(가로/2, 세로/2) 알맞은 색종이의 개수를 반환하면 된다.

cut_and_count 함수

• (x, y) 좌표를 시작 좌표로 입력 받아 입력 받은 종이들을 탐색한다.
• n은 현재 탐색하는 색종이의 길이이다.
• 현재 좌표의 색깔과 탐색하는 좌표의 색깔이 다르면 4분할을 시도한다.
  • 1, 2, 3, 4분면으로 나누기 위해 x, y 좌표, 그리고 n을 2로 나누어 조합한다.
    (x, y, n/2) (x, y+n/2, n/2) (x+n/2, y, n/2) (x+n/2, y+n/2, n/2)
• cut_and_count(x, y, n)의 모든 범위 안에 있는 색종이가 같은 색일 때까지 탐색한다.
• 탐색이 끝나고 cur_color가 0, 즉 하얀색이면 w 변수에 1을 더한다.
• 탐색이 끝나고 cur_color가 1, 즉 파란색이면 b 변수에 1을 더한다.

완성된 코드