BOJ 1074 Z
1074번: Z (acmicpc.net) 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 우연히 눈에 들어와서 다시 풀어보게 되었다. 3년전에는 시간초과로 풀지 못했었는데, 이번엔 간단히 풀 수 있었다. 요약하자면, 분할정복이다. Map을 4분할 했을때, r,c의 위치에 따라 r,c보다 앞쪽에서 탐색되는 좌표들의 개수를 대략적으로 알 수 있고, 그 다음 좌표를 shift시키면서 이를 반복한다면, 답을 구할 수 있다. 각 구역의 좌표들은 다음과 같은 특징을 가진다. 1구역 : r < 2^(n-1), c ..
