[백준] 1074번 - Z

📩 출처

문제

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

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

👉 생각

• 분할정복 문제라고 생각해서 n이 1일때까지 계속해서 사분면으로 분할을 하고 값을 채워주는 식으로 진행을 했다.
• 테스트케이스는 모두 통과했지만,,,시간초과

n, r, c = map(int, input().split())
arr = [[0]*(2**n) for _ in range(2**n)]
ans = 0

def dac(x, y, n):
    global cnt
    if n == 1:
        for dx, dy in [(0,0), [0,1], [1,0], [1,1]]:
            cnt += 1
            nx, ny = x + dx, y + dy
            arr[nx][ny] = cnt
    else:
        n -= 1
        dac(x, y, n)
        dac(x, y+(2**n), n)
        dac(x+(2 ** n), y, n)
        dac(x+(2 ** n), y+(2 ** n), n)

cnt = -1
dac(0, 0, n)
print(arr[r][c])

• 결국 이 문제는 재귀를 통해 값을 채우는 방식이 아닌 n이 줄어들때마다 r과 c의 값을 비교해서 가로 (혹은 세로)길이와 비교하는 4가지 방법을 생각해야 한다.
• 처음 n이 3이고 한번 분할을 하게 되면 n은 2가 되고 ans에 값을 추가시켜준다고 할때,

1. r < 2n and c < 2n이라면 우리가 찾는 값은 사각형을 기준으로 2사분면에 있을 것이다.
   • 2사분면의 값 ans + 0
2. r < 2n and c >= 2n이라면 우리가 찾는 값은 1사분면에 있을 것이다.
   • 1사분면의 값 ans + check*check
   • 2사분면의 끝의 마지막 값이 check*check -1 이기 때문!
3. r >= 2n and c < 2n이라면 우리가 찾는 값은 3사분면에 있을 것이다.
   • 3사분면의 값 ans + checkcheck2
4. r >= 2n and c >= 2n이라면 우리가 찾는 값은 4사분면에 있을 것임
   • 4사분면의 값 ans + checkcheck3

• n이 1일때까지 위 과정을 반복한다!

n, r, c = map(int, input().split())
ans = 0

while n != 0:
    n -= 1
    check = 2**n

    if r < check and c < check:
        ans += 0

    elif r < check and c >= check:
        ans += check * check
        c -= check

    elif r >=check  and c < check:
        ans += 2 * check * check
        r -= check
    else:
        ans += 3 * check * check
        r -= check
        c -= check
print(ans)