1074번 Z

Z

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	8341	3635	2364	43.154%

문제

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

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

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

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

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

2**N * 2**N인 판에서 Z방향으로 탐색할때 (r,c)좌표를 몇번째 만에 찾느냐? 문제이다.

문제를 보고 1개씩 순찰할 목적으로 2**N by 2**N 를 생성한다면 당신은 무슨 소스를 짜든 메모리 초과가 뜰것이다.

그렇다면 어떻게 해야할까?

우리는 주어진 가상의 matrix를 4개로 쪼갤수 있다는 것을 안다.

그것을 1사분면, 2사분면, 3사분면, 4사분면 이라고하자.

 만약 (r,c)가 1사분면에 있으면 다른 사분면을 둘러볼 필요가 없다.

(r,c)가 2사분면에 있으면 1사분면의 양만큼 이동한뒤 다시 2**N/2 by 2**N/2 matrix에서 (r,c- 2**N/2)의 좌표를 찾는 것과 같다.

이렇게 모두 둘러볼 필요없이 일정 범위 안이면 그전에 얼마만큼 대강 이동했는지 유추해가며

결국엔 2x2 matrix가 남는다.

거기서 남은 rc가 00 01 10 11인지 판단하여 0,1,2,3을 카운팅해주면 된다.

같은 로직이나 우리는 재귀로도 풀 수 있고, 그냥 반복문으로도 폴 수 있다. 

공간을 계속 저장해 놓을 필요가 없기 때문이다.

아래는 재귀소스이다.

import sys

sys.stdin = open("input.txt","r",encoding="utf-16")

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

cnt =0

def find_point(n):

global cnt

global r

global c

if n != 2:

if r < n/2:

if c < n/2:

find_point(n/2)

else:

cnt = cnt + (n/2)**2

c = c - n/2

find_point(n/2)

else:

r = r - n/2

cnt = cnt + n*(n/2)

if c < n/2:

find_point(n/2)

else:

cnt = cnt + (n/2)*(n/2)

c = c - n/2

find_point(n/2)

else:

if r==0:

if c==0:

pass

else:

cnt = cnt+1

else:

if c==0:

cnt = cnt+2

else:

cnt = cnt+3

find_point(2**N)

print(int(cnt))

아래는 반복문 소스이다.

import sys

sys.stdin = open("input.txt","r",encoding="utf-16")

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

cnt =0

n= 2**N

while True:

if n != 2:

if r < n/2:

if c < n/2:

n = n/2

else:

cnt = cnt + (n/2)**2

c = c - n/2

n = n/2

else:

r = r - n/2

cnt = cnt + n*(n/2)

if c < n/2:

n = n/2

else:

cnt = cnt + (n/2)*(n/2)

c = c - n/2

n = n/2

else:

if r==0:

if c==0:

pass

else:

cnt = cnt+1

else:

if c==0:

cnt = cnt+2

else:

cnt = cnt+3

break

print(int(cnt))