백준 1074 : Z

문제 링크

재귀 문제라고는 하지만, 백준 문제는 파이썬으로는 재귀함수를 써서 통과하기 참 어렵다..

r,c를 이용하여 그 위치의 숫자를 찾아내는 고민을 하던 중에 4덩어리로 나누는 아이디어가 생각났다.

n == 1
1 2
3 4

n == 2
4 8
12 16

n == 3
16 32
48 64

...

n을 줄여나가면서 4분면 좌표를 핀포인트로 잡을 수 있을 것 같다.

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

size = n
row = r + 1
col = c + 1

quadrant = []

while size > 0:
    if row > (2**size) // 2:
        if col > (2**size) // 2:
            quadrant.append(4)
            row -= (2**size) // 2 ## 4분면 내에서의 행.열의 상대적 위치를 갱신
            col -= (2**size) // 2
        else:
            quadrant.append(3)
            row -= (2**size) // 2
    else:
        if col > (2**size) // 2:
            quadrant.append(2)
            col -= (2**size) // 2
        else:
            quadrant.append(1)
    size -= 1

이렇게 하면 quadrant 리스트에 n,r,c에 대응하는 4분면 좌표가 저장된다.

'''
input
3 7 7
'''

# quadrant => [4,4,4]
# => 4**3(8*8) 행렬의 4분면의 4분면의 4분면에 존재!

'''
input
2 3 1
'''

# quadrant => [3,4]
# => 4**2(4*4) 행렬의 3분면의 4분면에 존재!

4분면 좌표를 안다면 각 단계의 끝 숫자를 역추적할 수 있다.

start = 4 ** n
for i in range(len(quadrant)):
    start -= 4**(len(quadrant)-1-i)*(4-quadrant[i])

# 0부터 시작하니 1 빼주기
print(start-1)

'''
input
3 7 7
output
63
'''