[BJ] 1780 - 종이의 개수 (재귀 분할정복)

 

 

문제풀이

분할 정복 알고리즘과 재귀를 이용하여 해결하는 문제이다.

분할 정복 알고리즘이란 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다.

이 문제에 따르면

1. 종이(배열) 안의 숫자들이 모두 같다면, 그 종이는 분할하지 않고 넘어간다.
2. 종이 내에 다른 숫자가 하나라도 포함된다면, 그 종이를 9분할 한다.
3. 9분할한 종이 하나하나마다 숫자가 같은지 확인한다.(다시 1번으로 반복)

9*9 크기의 종이를 예로 들면,

9*9 크기에 채워진 숫자들, 즉 81칸의 숫자가 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++

하나라도 다르다면 3*3 크기의 종이 9개로 분할 (즉 3^n승이니 한변의 길이는 n/3이다)

3*3 크기의 종이 하나하나 다시 체크 -> 모두 같다면 -> n으로만 적혀있는 종이의 개수 ++ -> 다음 종이로 넘어감

하나라도 다르다면 1*1 크기의 종이 9개로 분할

1*1이 된다면 칸이 하나밖에 없기 때문에 모두 같을 수밖에 없어 더 이상 분할하지 않는다.

즉 1*1 크기로 분할할 때까지 과정을 반복하는 것.

 

 

 

n이 되면 n + 1도 되는지 귀납적으로 계속 생각하자..