[백준 1074] 파이썬 - Z

https://www.acmicpc.net/problem/1074

1074번: Z

 

 

# 조건

• 크기가 2^N x 2^N 배열을 Z모양으로 탐색
• 왼쪽위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 탐색하면 된다.
• N>1 인 경우, 배열을 크기가 2^(N-1) x 2^(N-1)로 4등분 한 후 재귀적 순서대로 방문
• r행 c열을 몇 번쨰로 방문하는지 출력

 

# 접근 방법 및 Solution

• 2^(N-1) x 2^(N-1) 로 나눠서 생각 해준다.
• 결국 1, 2, 3, 4, 분면에 따라 최소, 최대의 값이 정해진다.
• 좌표 값을 이용하여 사분면을 나눠주고, 사분면의 시작하는 값을 구해준다.
• 시작하는 값 -> 이전까지의 칸의 개수이므로 num += 2 ** (N - b) * 2 ** (N - b) * 1 와 같이 사분면에 따라 1씩 증가시켜주며 누적합을 구해주면된다.

 

N, r, c = map(int, input().split())  
  
num = 0  
b = 1  
# 인덱스 이용 사분면 나눠주기  
while N-b >= 0:  
    # 1사분  
    if r < 2**(N-b) and c < 2**(N-b):  
        # 나눠진 사분면의 시작하는 수  
        num += 2**(N-b) * 2**(N-b) * 0  
    # 2  
    elif r < 2 ** (N - b) and c >= 2 ** (N - b):  
        c -= 2 **(N-b)  
        num += 2 ** (N - b) * 2 ** (N - b) * 1  
    # 3  
    elif r >= 2**(N-b) and c < 2**(N-b):  
        r -= 2 ** (N - b)  
        num += 2**(N-b) * 2**(N-b) * 2  
    # 4  
    elif r >= 2**(N-b) and c >= 2**(N-b):  
        c -= 2 ** (N - b)  
        r -= 2 ** (N - b)  
        num += 2**(N-b) * 2**(N-b) * 3  
  
    b+=1  
  
print(num)

 

 

# 다른 사람 풀이 - 재귀 이용

• 0을 제외한 좌표 r, c 가 2배가 됨에 따라 값이 4배로 확장
• 8 (2,0) -> 32(4,0)

N, r, c = map(int, input().split())  
  
  
def sol(N, r, c):  
    if N == 0:  
        return 0  
  
    return 2 * (r % 2) + (c % 2) + 4 * sol(N - 1, int(r / 2), int(c / 2))  
  
  
print(sol(N, r, c))

 

• 여기서 2 * (r % 2) + (c % 2)는 화살표와 같다.