백준 1074 Z

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

1074번: Z

 

음 ~

 

음 ~~~~~?

 

 

 

 

음~~~?

 

무튼 시작..!

 

처음에 분할해서 가장 작은 2*2사각형에서부터 배열을 합쳐가면서 만족하는 좌표를 찾아봐야지했는데 뭔가 구현을 어떻게 해야할지 감이 안잡히다가 팀원들이 푼방식을 보고 힌트..? ..를 보고 ...풀었다

 

그래서 수정한 아이디어는 좌표의 상대적인 위치에다가 보정값을 맥여주면서 재귀호출을 수거하면서 쌓인 보정값을 더해주면서 리턴해준다는것. 말로설명하면 뭔가 이해가 안될거같아서.. 그림..준비했다 !

 

만약 N이 3일때 (6,7) 의 60이라는 값을 호출해야한다면 ..

호출되는 시점으로 생각 하면 (6, 7) 의 위치를 1/4 씩 감소시켜가면서 1/4된 사각형이 몇배수에 있는 사각형인지만 체크하면서

N=0까지 사각형을 나눈다.

왼쪽은 호출하면서 분할해가는 느낌이고 오른쪽은 재귀 종료후 회수되는 시점이다.

 

 

이렇게 생각 하고 문제를 풀면서 고생했던건.. 자르는 범위의 조절이였다.. 자르는 중심값 근처의 기준을 어디 영역에 포함시킬지 사실 디버그모드로 찍어보면서 푼듯하다... 인덱스생각하면서 계산했으면 좀 더.. 덜 고생했을텐데 ..

 

아래는 해당코드..이다

def z(n,r,c)->int:
    if n==0:
        return 0;
    half_length = (2 ** n)//2
	#3
    if half_length<= c and half_length <= r :
        d=3
    
        sum=d*(4**(n-1))
        return sum+z(n-1,r-half_length,c-half_length)
    #0 
    elif half_length > c and half_length > r :
        d=0
        sum = d * (4 ** (n - 1))
        return sum + z(n - 1, r, c)
    #2
    elif c < half_length <= r:
        d=2
        sum = d * (4 ** (n - 1))
        return sum +z(n - 1, r - half_length, c)
    #1
    elif c >= half_length> r:
        d=1
        sum = d * (4 ** (n - 1))
        return sum +z(n - 1, r ,c- half_length)
while(True):
    n,r,c=map(int,input().split())
    print(z(n,r,c))