백준 1074. Z

tose33 2022. 10. 10. 14:22

1074번: Z

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을

www.acmicpc.net

시간을 보면 일일히 한칸씩 옮겨다니며 숫자를 세면 시간초과가 날것이다.

이 문제는 재귀적으로 해결해야 한다.

1. 한 변의 길이가 2*n인 정사각형에서 우리가 구하는 (r,c)가 몇 사분면에 있는지 구한다.

2. 해당 사분면에서에 해당하는 한 변의 길이 (2*(n-1)) 정사각형에서 (r,c)가 몇 사분면에 있는지 구한다.

3. 위 과정을 n=0 이 될때까지 반복한다.