[백준/1074/파이썬] Z

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

1074번: Z

Problem

• 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
• N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

조건

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

SOL

분할정복의 개념이 쓰이기는 하지만, 결국은 규칙을 찾아내는 문제였다.

"분할정복"이라고 했을 때, 직관적으로 "분할해서, 문제를 해결해야한다" 개념이 아주 짙은 문제였다.

이때, 재귀적으로 구현을 할 수도 있고, 규칙성을 나타낼 수 있다면, 반복문을 써도된다.

 

이 문제는 2^N *2^N 크기의 배열을 4등분하고, 또 4등분하고 ... 이런식으로 해서, Z자 모양으로 순차적을 방문했을 때, R,C가 몇번째로 방문되는지 알아내는 문제이다.

우선 4등분을 한다니까, 4가지 구역으로 나눌 수 있을 거고, 각 구역의 시작점을 보면, 규칙성이 발견이 된다.

좌표평면처럼 , 4등분된 구역을 1사분면 ~ 4사분면으로 부르도록 하겠다.

 

 

1사분면의 시작점은 0 = 4*4*0

2사분면의 시작점은 16 = 4*4 * 1

3사분면의 시작점은 32 = 4*4* 2

4사분면의 시작점은 48 = 4*4* 3

 

즉, 4등분한 크기의 제곱의 0~3곱으로 표현할 수 있다.

Psudo code로 간단히 작성하면 아래와 같이 될거다.

## Psudo code
if 1사분면:
	ans+=(크기)^2 *0
if 2사분면:
	ans+=(크기)^2 *1
if 3사분면:
	ans+=(크기)^2 *2
if 4사분면:
	ans+=(크기)^2 *3

 

이때, 우리가 찾고싶은 좌표 (R,C)도 해당 좌표에 맞게 설정을 해줘야 하게 된다.

 

예를들어, R= 0, C=5 인 17이라면, 큰 사각형에서 봤을 때는 17번째지만, 2사분면을 다시 4등분해서 쪼개면, 

1사분면에 있게되고, 시작점(16)을 0이라고 했을때, 17은 1이 된다.

즉, C의 좌표도 압축을 해줘야한다.

## Psudo code
if 1사분면:
	#압축 필요없음
	ans+=(크기)^2 *0
if 2사분면:
	x좌표 압축
	ans+=(크기)^2 *1
if 3사분면:
	y좌표 압축
	ans+=(크기)^2 *2
if 4사분면:
	y,x좌표 압축
	ans+=(크기)^2 *3

 

위의 Psudo Code를 코드로 나태내면 아래와 같다!

 

# "Z"

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

while N !=0:
    N -=1
    if 0<=R<2**N and 0<=C<2**N:
        cnt+=(2**N) * (2**N) *0
    if 0<=R<2**N and 2**N<=C<2**(N+1):
        cnt+=(2**N) *(2**N) *1
        C-=2**N
    if 2**N<=R<2**(N+1) and 0<=C<2**N:
        cnt+=(2**N) * (2**N) *2
        R-=2**N
    if 2**N<=R<2**(N+1) and 2**N<=C<2**(N+1):
        cnt += (2**N) *(2**N) *3
        C-=2**N
        R-=2**N

print(cnt)