[백준][Python] 1074 Z

# 문제 링크

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

 

# 문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

 

# 입력

첫째 줄에 정수 N, r, c가 주어진다.

 

# 출력

r행 c열을 몇 번째로 방문했는지 출력한다.

 

# 범위

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

 

# 예제

예제입력	예제출력
2 3 1	11
3 7 7	63
1 0 0	0
4 7 7	63
10 511 511	262143
10 512 512	786432

 

---

# 문제 풀이

https://github.com/taerimiiii/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Gold/1074.%E2%80%85Z

Algorithm/백준/Gold/1074. Z at main · taerimiiii/Algorithm

 

문제에서도 대놓고 재귀라 쓰여 있다. 2의 n승을 1이 될 때까지 계속 2로 나누면서 조건 처리해 주면 되는 문제다. 재귀함수.. 아직 쓰기 어려워서 그냥 반복문으로 풀었다.

 

import sys
input = sys.stdin.readline

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

cnt = 0
n = 2 ** n

while n > 1 :
	n //= 2

    # 왼 위
	if r < n and c < n :
		cnt += 0 # 더할 공간이 없다

    # 왼 아래
	elif r < n and c >= n : 
		cnt += n * n * 2 # 사분면 기준 '왼 위'와 '오른 위' 공간을 더해 준다. 
                         # n X n 정사각형 2개
		c -= n
        
    # 오른 위
	elif r >= n and c < n : 
		cnt += n * n * 1 # 사분면 기준 '왼 위' 공간을 더해 준다. 
                         # n X n 정사각형 1개
		r -= n
        
    # 오른 아래
	else:
		cnt += n * n * 3 # 사분면 기준 '왼 위'와 '오른 위', '왼 아래' 공간을 더해 준다. 
                         # n X n 정사각형 3개
		r, c = r - n, c - n
    
print(cnt)

이 문제는 반복문으로도 풀리지만 재귀함수를 연습해 보는게 좋을 것 같아서, 지피티야 재귀함수로 바꿔줘~~ 시전해서 공부해 보았다.

 

재귀함수 코드

import sys
input = sys.stdin.readline

def z(n, r, c):
    # n: 현재 2^n 크기의 정사각형
    if n == 0:
        return 0

    half = 2 ** (n - 1)
    size = half * half

    # 1사분면 (좌상단)
    if r < half and c < half:
        return z(n - 1, r, c)

    # 2사분면 (우상단)
    elif r < half and c >= half:
        return size + z(n - 1, r, c - half)

    # 3사분면 (좌하단)
    elif r >= half and c < half:
        return 2 * size + z(n - 1, r - half, c)

    # 4사분면 (우하단)
    else:
        return 3 * size + z(n - 1, r - half, c - half)

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