백준 1074 Z 파이썬

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

 

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다.

 

예제 입력	예제 출력
2 3 1	11
3 7 7	63
1 0 0	0
4 7 7	63
10 511 511	262143
10 512 512	786432

 

문제 바로가기

---

탐색 방법

해당 문제를 분할하여 재귀 알고리즘으로 값을 구하도록 구현했다. 작은 상자로 나눠 어떤 규칙에 따라 값이 증가하는지 찾으려고 노력했다. 먼저 2X2 박스씩 확인하여 규칙을 찾았다. 행과 열이 2배가 되면, 상자 안의 값이 4의 배수로 늘어난다.

• • 3 (1, 1) → 12 (2, 2)
  • 7 (1, 3) → 28 (2, 6)

코드 구현

위에서 2X2 상자로 나누어 확인했던 것처럼, 상자칸에서 이동하는 것이 가장 작은 단위의 코드라고 할 수 있다.

• a, b를 좌표라고 가정했을 때, 옆 칸으로 이동하는 코드를 2 * (a%2) + (b%2)로 구현
• 4의 배수하기 이전의 좌표가 (a//2, b//2)이므로, 4의 배수한 후의 값은 4 * solve(n-1, a//2, b//2)로 구현

⭐ 옆 칸으로 이동하는 코드에서 왜 a%2는 곱하고, b%2는 더하나요?

그건 모양이 Z이기 때문이다. 만약 N을 상하로 뒤집은 모양이었다면 2 * (b%2) + (a%2)로 구현해야 할 것이다.

 

전체 코드

import sys
input = sys.stdin.readline

# 2의 승, 행, 열
n, r, c = map(int, input().split())

def solve(n, a, b):
    if n == 0:
        return 0
    else:
        return (2 * (a%2) + (b%2)) + (4 * solve(n-1, (a//2), (b//2)))
    
print(solve(n, r, c))