Baekjoon 1074번 Z

문제

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

걸린 시간

02 : 16 : 02

풀이

Python3

def zsearch(start, side, loc, r, c):
    arr_size = side**2
    quarter = arr_size//4

    # 2x2 크기까지 나누어지면
    if side//2 == 1:
        z_s = start # z start
        for i in range(loc[0], loc[0]+2):
            for j in range(loc[1], loc[1]+2):    
                if i == r and j == c:
                    print(z_s)
                z_s += 1
    else:
        index = 0
        s_l = [] # start list
        for s in range(start, start+arr_size, quarter): # ex) 0, 64, 16
            s_l.append(s)

        for i in range(loc[0], loc[0]+side, side//2):
            for j in range(loc[1], loc[1]+side, side//2):
                if i <= r and j <= c and i+(side//2) >= r and j+(side//2) >= c:
                    zsearch(s_l[index], side//2, [i, j], r, c)
                index += 1

if __name__ == "__main__":
    N, r, c = map(int, input().split())    

    side = 2**N
    zsearch(0, side, [0, 0], r, c)

2n x 2n 크기의 배열에 모든 값을 기록하고 r, c 좌표로 접근하려고 했지만 메모리 초과가 났다.

n의 최대 입력인 15가 들어오면 어마어마한 크기의 2차원 배열이 만들어지기 때문이다.

2차원 배열이 존재한다고 가정하고 문제를 풀어야 한다.

재귀 호출도 찾으려는 좌표가 범위 내에 존재할 경우에만 호출, 배열에 값을 기록하는 대신 찾으려는 좌표 값과 비교해 일치할 때만 출력 하면된다.