1. 문제 설명
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
2. 아이디어
일전에 다루었던 색종이 자르기 문제(BOJ - 2630)와 유사하다.
분할 탐색을 하되, 시간 제한이 0.5초밖에 안 되기 때문에 여유롭게 처음부터 읽고 있다가는
곧바로 시간 초과로 탈락할 수 있다.
사실 너무 뻔한 방법이다.
4분할을 했을 때 그곳에 내가 탐색하고자 하는 좌표가 포함되지 않는 사분면이라면
탐색하지 않고 건너뛰고, 해당 타일의 전체 개수만 계산해서 결과에 더하면 된다.
알고리즘에 대해 조금 공부해본 사람이라면 이런 문제는 구현에서 막힐지언정
크게 아이디어가 필요한 문제는 아니었다.
3. 코드
n, r, c = map(int, input().split())
cnt = 0
def divide_recursive(row, col, limit):
global cnt
if row == r and col == c:
print(cnt)
exit(0)
if limit == 1:
cnt += 1
return
if (row <= r < row + limit and col <= c < col + limit):
divide_recursive(row, col, limit//2)
divide_recursive(row, col + limit//2, limit//2)
divide_recursive(row + limit//2, col, limit//2)
divide_recursive(row + limit//2, col + limit//2, limit//2)
return
else:
cnt += pow(limit, 2)
return
def solution():
global n
divide_recursive(0, 0, pow(2, n))
solution()