백준 - Z

문제 출처: https://www.acmicpc.net/problem/1074

1074번: Z

 

분할 정복을 이용한 재귀 문제이다.

초기 의사 코드는 행, 열 길이가 2일 때까지 재귀를 타고 들어가서, 0,0부터 4분 할로 접근하는 방식을 선택하였다.

이 방식은 결국 시간 초과로 실패...

 

지문을 제대로 보니 2^N X 2^N의 최대 크기를 가질 수 있으므로 당연히 가지치기(?)가 매우 중요하다.

또한 배열을 사용하지 않는데 처음에 배열을 만들어서 계속 메모리 초과가 발생했다..

 

시간을 단축시킬 방법을 생각해보다 애초에 모든 시작을 0,0이 아니라 4 사분면으로 나눴을 때 목표 좌표가 속해있는 사분면으로 가면 되지 않을까?라는 생각을 하게 되었다.

 

 

조건에 따라 어느 사분면으로 이동할지 정해주고, 각 좌표의 숫자 또한 정해주었다.