[2630]. 색종이 만들기

[1. 문제 설명]

정사각형 모양의 2차원 배열에서 같은 색깔로 구성 된 정사각형의 개수를 찾는 문제.

정사각형 한변의 길이는 최대 128이고, 현재 정사각형이 모두 같은 색깔로 구성되지 않은 경우,

4등분하여 검사한다.

 

 

[2. 풀이 접근]

 

• 재귀로 접근
• 재귀의 탈출 조건, 정사각형 한변의 길이가 1인 경우
• 2차원 배열 내 모든 값의 합이 0 이거나, N^2 이면, 모두 같은 색깔로 이루어진 것을 판별할 수 있다.
  => 배열이 크지 않으니, 시간 상 큰 문제 없다고 생각함.
• 모든 색깔이 같은 경우, 정사각형 내 아무 원소나 선택 하여 그 색깔을 알 수 있다.
• 모든 색깔이 같지 않은 경우, 분할 후 재귀로 처리한다. 

 

 

 

[3. 코드]