[Baekjoon 1074 / Python / 골드5] Z

문제

# 정사각형 한 변의 길이 : 2, 4, 8 ....

import sys

input = sys.stdin.readline

# 2의 N승 크기, R행 C열

N, R, C = map(int, input().split())

# 행/열이 길이 나누기 2이상이면 -> 행 : 아래쪽 사분면/ 열 : 오른쪽 사분면

le = 2**N

# 결과값 편하게 더하기 위해 만든 배열

num = [[0,1], [2,3]]

# 각사분면 0,0값, 변길이, 행, 열

def divide(z, le, row, col):

    if le == 2: # 2*2 정사각형 도달 시

        print(z + num[row][col])

        return

    plus = (le * le) // 4 # 각 사분면 0,0 값의 차이

    half = le // 2

    if row >= half:

        if col >= half:

            # 우측아래 사분면

            divide(z+(plus*3), half, row-half, col-half)

        else:

            # 좌측아래 사분면

            divide(z+(plus*2), half, row-half, col)

    elif col >= half:

        # 우측위 사분면

        divide(z+plus, half, row, col-half)

    else:

        # 좌측위 사분면

        divide(z, half, row, col)

divide(0, le, R, C)

 

분할 정복 문제이다.

 

z는 각 사분면의 0,0 값을 의미한다.

plus는 각 사분면의 0,0 값의 차이를 의미한다. 변의 길이를 알면 쉽게 구할 수 있다. 재귀호출을 하면서 z에 plus를 더해주는 것을 볼 수 있다.

4등분 할 때마다 row, col(행,열) 좌표를 수정해 주어야 한다. half(변의 길이 // 2) 보다 row가 크다면 row-half 를 해주면 된다. col도 마찬가지다. 이렇게 하면 4등분을 해도 처음 지정했던 좌표가 고정될 수 있다.

 

결국 가장 작은 사각형인 2*2 사각형이 되면, row와 col은 [0,0], [0,1], [1,0], [1,1] 이 4개 값중에 하나가 된다. 

z변수에 사분면의 0,0 값을 꾸준히 계산해 두었기 때문에, 좌표에 따라서 z에 0~3을 더해서 출력만 해주면 된다.

 

정리하자면 2*2 사각형이 될 때까지 4등분하면서 row, col값과 z 값을 계속해서 갱신해주면 된다.

 

 

결과