백준 1074번: Z

문제 설명

• Z모양으로 이동한다는 건 (0,0) -> (0,1) -> (1,0) -> (1,1) 순서로 이동하는 걸 의미합니다.

접근법

• 재귀를 활용할 수 있습니다.
• 정사각형 단위로 데이터를 처리한다는 점에서 쿼드 압축과 유사한 부분이 있습니다.
  • 개인적으로 프로그래머스의 쿼드압축 후 개수 세기를 풀어보는 걸 추천합니다.
• 1,2,3,4사분면 중 어느 곳에 위치하는지를 계속 파악해야 합니다.
  • 행이 사각형의 절반을 넘으면 3,4분면에 존재합니다.
  • 열이 사각형의 절반을 넘으면 1,2분면에 존재합니다.
• 구하는 값이 n분면에 있다면 n-1분면까지의 값을 모두 더하고 n분면에서의 위치만 계산하면 됩니다.

정답

N,r,c = list(map(int,input().split(" ")))
answer = -1
def quadrant(r,c): #몇사분면에 있는지를 계산합니다
    if r == c == 0:
        return 0
    elif r == 0 and c == 1:
        return 1
    elif r == 1 and c == 0:
        return 2
    else:
        return 3

def Z_func(N,r,c,answer):
    if N == 0: #N이 0일 경우가 종료조건입니다.
    	# (2**(2*N-2))은 한 사분면의 크기입니다
        return int(answer + (2**(2*N-2))**quadrant(r,c))
    
    #div로 몇분면에 위치하는지, mod로 해당 분면의 어디에 위치하는지를 표시합니다.
    r_div,r_mod = divmod(r,2**(N-1))
    c_div,c_mod = divmod(c,2**(N-1))
    answer += (2**(2*N-2))*quadrant(r_div,c_div)
    return Z_func(N-1,r_mod,c_mod,answer)

print(Z_func(N,r,c,answer))

기타

• quadrant를 분기 없이 구현할 수 없을까?