[python] 백준 1074 :: Z

[Z]

# 문제
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

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

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

풀이

전체 코드

N, r, c = map(int, input().split())


def recursive(n, row, col):
    if n == 0:
        return 0
    cur_count = 2 * (row % 2) + (col % 2)
    return 4 * recursive(n-1, row // 2, col // 2) + cur_count


print(recursive(N, r, c))

1. 표의 규칙 찾기

문제에서 주어진 정보는, 어떤 크기의 표가 주어지는지와 행과 열의 인덱스이다.
이것들을 활용할 수 있는 규칙을 찾아야 한다.

• 어떤 한 위치에서 행과 열에 각각 2를 곱한 위치의 값은 기존 값의 4배이다.

• 이 규칙을 이용해서 역으로 찾아가보자!
  어떤 한 위치에서 행과 열을 각각 2로 나눈 위치의 값은 기존 값의 1/4배이다.

• 이렇게 점차 1/4씩 줄여나가면서 우리가 값을 알고 있는 0~3까지 줄어들 때까지 줄여가서 값을 찾고,
  4로 나눈 만큼 4를 다시 곱해주면 찾으려는 행과 열에 해당하는 값을 알 수 있다.
• 값을 알고 있는 0~3이 될 때까지 줄여가는 횟수는 간단하다.
  2의 N승 × 2의 N승인 2차원 배열이므로, N회 반복하면 된다! (N을 1씩 줄여나가면서 0이 되면 종료)

# 지금은 답이 0이 된다, 아래 단계에서 코드를 추가해야 한다.
def recursive(n, row, col):
    if n == 0:
        return 0
    return 4 * recursive(n-1, row // 2, col // 2)

• 그런데, 63처럼
  각 행과 열이 2로 나누어떨어지지 않을 때는 어떻게 찾아야 할까?

• 작은 Z 기준으로 맨 왼쪽 위에 위치하는 지점으로 살짜쿵 돌아가서 찾아줘야 한다.
  (행과 열을 어떻게든 2로 나눌 수 있게 만들어야 한다🤮)
• 63의 경우에는, Z를 그렸을 때 60이 시작이므로 60에 해당하는 (6,6)에서 반씩 나눈 행과 열 (3,3)을 찾고, 차이인 3만큼 더해주면 된다.

예시

(3, 3)의 값을 알고 있다고 가정해보자.

이때 (7, 7)의 값을 도출하는 방법은

# (3, 3)의 값인 15에 4를 곱해주고 👉🏻 4로 나눈 값이니까!
# 3을 더해준다. 👉🏻 Z의 끝에서 처음으로 돌렸으니 -3을 한 셈

(15 * 4) + 3

Z의 어느 지점으로 돌아가야 하는 순간인지 따로 계산할 필요는 없다.
그냥 각 행과 열을 몫 연산자 // 를 이용해서 몫만 구해주면 되니까!
경우에 따라서 더해줘야 하는 값은 밑에서 따로 계산할 거임!!

이 과정을 우리가 값을 알고 있는 0~3이 나올 때까지 반복해주면 된다. (1/4배 할 때마다 문제에서 주어지는 N을 1씩 줄여나가서 N이 0이 될 때까지 하면 된다.

이제 다음 단계로, Z의 기존 위치만큼 다시 더해줄 값을 구하는 방법을 알아보자!!

더해줄 값 찾는 방법

• 우선 맨 왼쪽 위에 있는 작은 Z에서 규칙을 찾아보자!
• 주어지는 정보가 행과 열이니, 행과 열을 이용해서 표 안의 값을 알아낼 규칙이 필요하다.
• 위 경우에는 (2 * 행_인덱스 ) + 열_인덱스 로 구할 수 있다.
• 그렇다면, 행과 열이 0, 1이 아니라면?

• 행과 열을 2로 나눈 나머지로 동일하게 구해주면 된다.
• 이렇게 구한 더해줄 값을 위에서 구한 1/4배를 N번 해서 찾은 값에 1/4배 한 만큼 다시 4를 곱해주고,
  더해주면 된다.
  4 * 1/4배 해서 찾은 값 + 더해줄 값

def recursive(n, row, col):
    if n == 0:
        return 0
    cur_count = 2 * (row % 2) + (col % 2)
    return 4 * recursive(n-1, row // 2, col // 2) + cur_count

끝!!

전체 코드

N, r, c = map(int, input().split())


def recursive(n, row, col):
    if n == 0:
        return 0
    cur_count = 2 * (row % 2) + (col % 2)
    return 4 * recursive(n-1, row // 2, col // 2) + cur_count


print(recursive(N, r, c))