[Python/Baekjoon] 1074. Z

💬 문제

문제 난이도: 백준 실버 1

❗️접근 방법

위의 예시는 인풋으로 주어진 N이 2인 경우이다.
2^N X 2^N 크기의 정사각형에서 r번째 행과 c번째 열에 있는 숫자가 무엇인지를 구하면 된다.

위의 규칙을 보면, 정사각형을 한 변의 길이가 2인 사각형으로 계속해서 4분할할한다는 것을 알 수 있다.
또한 4분할된 사각형을 왼쪽위-> 오른쪽위 -> 왼쪽아래 -> 오른쪽아래 순으로 순회한다는 것을 알 수 있다. (Z모양으로)

r, c과 주어졌으므로 해당 row와 col에 속해 있을 사분면을 찾아내면 된다.

근데 이제 재귀를 곁들인

✅ 내 코드

import sys
input = sys.stdin.readline

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

result = 0
def solution(r, c, n):
    global result
    
    # 정사각형의 한 변의 길이가 1일 때 (2^0 == 1)
    if n == 0:
        return
        
    #0 : 왼쪽위
    if 0<=r< pow(2, n-1) and 0<=c<pow(2, n-1):
        solution(r, c, n-1)

    #1 : 오른쪽위
    elif 0<=r<pow(2, n-1) and pow(2, n-1)<=c<pow(2,n):
        c -= pow(2, n-1)
        result += pow(2, n-1)**2 * 1
        solution(r, c, n-1)

    #2 : 왼쪽아래
    elif pow(2, n-1)<=r<pow(2,n) and 0<=c<pow(2, n-1):
        r -= pow(2, n-1)
        result += pow(2, n-1)**2 * 2
        solution(r, c, n-1)
        
    #3 : 오른쪽아래
    else:
        r -= pow(2, n-1)
        c -= pow(2, n-1)
        result += pow(2, n-1)**2 * 3
        solution(r, c, n-1)

solution(r, c, N)
sys.stdout.write('{}'.format(result))

#1, #2, #3에서 r 혹은 c를 갱신하는 이유

4분할 되면서 한 변의 길이가 반으로 줄어든다.
이때 #0에 속하게 되면 찾고자 하는 r과 c는 갱신될 필요가 없다.
하지만 다른 경우는 갱신되어 한다.
가령 #1에 속한다면, #1에서는 col의 인덱스가 2^(N-1)로 시작하기때문에 그만큼 빼줘야 한다.
가령 #3에 속한다면, #3에서는 row의 인덱스와 col의 인덱스 모두 2^(N-1)로 시작하기때문에 그만큼 빼줘야 한다.

#1, #2, #3에서 result 갱신하는 이유

다음 재귀함수로 넘어가기 전에, 해당 사분면의 (0, 0)에 해당하는 값을 result해 더해줘서 자취?를 남겨놓기 위함이다.