파이썬 백준 1074번: Z

문제

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

1074번: Z

 

 

풀이

사각형을 크게 네부분으로 나누면서 해당 구역의 값을 찾았다.

예제 입력 2 '3 7 7' 의 예시를 살펴보자.

처음 target은 4(48~63)구역이고 이또한 4부분으로 나누면 결국 구하고자 하는건 [[60,61],[62,63]]에서 임을 알 수 있다.

마지막으로 4번째 구역인 63을 얻어낼 수 있다.

 

num은 구하고자 하는 r행 c열의 수이다.

import sys

N,r,c=map(int,sys.stdin.readline().split())

num=0
while(N>0):
    N -= 1
    target=2**(N)
    if r<target and c<target : #1
        num=num
    elif r<target and c >=target : #2
        num+=target * target
        c-=(2**N)
    elif r>=target and c < target : #3
        num += target * target*2
        r-=(2**N)
    elif r>=target and c >=target : #4
        num +=target * target * 3
        c -= (2 ** N)
        r -= (2 ** N)

print(num)

 

 

 

🤔덧)

처음엔 2^(N-1) x 2^(N-1) 테이블을 그려서 메모리 초과가 발생했다. 

import sys
sys.setrecursionlimit(1000000000)

def searching(i,j):
    global num
    if r==i and c ==i:
        return
    if j>=(2**(N-1)) or i>=(2**(N-1)) or j<0 or i<0:
        return
    num_list[i][j]=num
    num+=1
    num_list[i][j+1]=num
    num+=1
    num_list[i+1][j]=num
    num+=1
    num_list[i + 1][j+1]=num
    num+=1
    searching(i,j+2)
    searching(i+2, j-(2**(N-1)-2))


N,r,c=map(int,sys.stdin.readline().split())
num_list=[]

max=r
if c>max:
    max=c
for i in range(2**(N-1)):
    temp=[0]*(2**(N-1))
    num_list.append(temp)


if r<2**(N-1) and c<2**(N-1) : #1사분면
    num=0
elif r<2**(N-1) and c >=2**(N-1) : #2사분면
    num=2**(N-1) * 2**(N-1)
elif r>=2**(N-1) and c < 2**(N-1) : #3사분면
    num = 2 ** (N - 1) * 2 ** (N - 1)*2
elif r>=2**(N-1) and c >= 2**(N-1) : #4사분면
    num = 2 ** (N - 1) * 2 ** (N - 1) * 3

searching(0, 0)
#print(num_list)
print(num_list[r%(2**(N-1))][c%(2**(N-1))])

c의 범위가 지정된 것으로 문제풀이의 힌트를 얻었다

더 작은 범위로 생각할 수 있는지 한번더 생각할것!