1074 : Z (Recursive) [C,C++]

먼저 방문 할 인덱스들의 행,열 값을 입력하면

길이가 2일 때(입력 값이 1일 때)

(0,0), (0,1)
(1,0), (1,1)

길이가 4일 때(입력 값이 2일 때)

(0,0), (0,1), (0,2), (0,3)
(1,0), (1,1), (1,2), (1,3)
(2,0), (2,1), (2,2), (2,3)
(3,0), (3,1), (3,2), (3,3)

길이가 8일 때(입력 값이 3일 때)

(0,0), (0,1), (0,2), (0,3), (0,4), (0,5), (0,6), (0,7)
(1,0), (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7)
(2,0), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6), (2,7)
(3,0), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (3,7)
(4,0), (4,1), (4,2), (4,3), (4,4), (4,5), (4,6), (4,7)
(5,0), (5,1), (5,2), (5,3), (5,4), (5,5), (5,6), (5,7)
(6,0), (6,1), (6,2), (6,3), (6,4), (6,5), (6,6), (6,7)
(7,0), (7,1), (7,2), (7,3), (7,4), (7,5), (7,6), (7,7)

빨간색 부분이 계속 나오는 것을 알 수 있습니다. 

그래서 재귀함수를 써야합니다.

재귀적으로 부를 소스를 보면

void Z::GetCount(int row, int column, int size)
{
 if (size == 2)
 {
  if (!this->IsEnd)
  {
   this->Count++;
   if (row == this->Target[0] && column == this->Target[1])
    this->IsEnd = true;
  }
  if (!this->IsEnd)
  {
   this->Count++;
   if (row == this->Target[0] && column + size / 2 == this->Target[1])
    this->IsEnd = true;
  }
  if (!this->IsEnd)
  {
   this->Count++;
   if (row + size / 2 == this->Target[0] && column == this->Target[1])
    this->IsEnd = true;
  }
  if (!this->IsEnd)
  {
   this->Count++;
   if (row + size / 2 == this->Target[0] && column + size / 2 == this->Target[1])
    this->IsEnd = true;
  }
 }
 else if(size > 2)
 {
  GetCount(row, column, size / 2);
  GetCount(row, column + size / 2, size / 2);
  GetCount(row + size / 2, column, size / 2);
  GetCount(row + size / 2, column + size / 2, size / 2);
 }
}

<소스 코드>

size가 2라는 말은 길이가 2라는 말입니다.

길이가 2인 행렬 2*2는 4가지의 인덱스로 구성되어 있는데

4가지의 인덱스에 다시 재귀함수를 써 접근했더니 

시간 초과가 떠서 이런 식으로 풀었습니다.

*Source of the problem = https://www.acmicpc.net/problem/1074

*문제 출처 : BAEKJOON ONLINE JUDGE