[python] 백준 알고리즘 1074번 Z, 다이나믹 프로그래밍 풀이법

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

1074번: Z

N, r, c = map(int, input().split())
M = {1: 0}

def Z(n, x, y):
    if n in M:
        return M[n]
    else:
        n //= 2
        for i in range(2):
            for j in range(2):
                if x < n*(i+1) and y < n*(j+1):
                    ret = (2*i+j)*(n*n) + Z(n, x-n*i, y-n*j)
                    M[n] = ret
                    return ret

print(Z(2**N, r, c))

dictionary M = {1:0}을 정의 해주고,

n값이 M안에 있다면, key값으로 찾아서 value값을 반환해준다.

n이 1인 값부터 전부 저장해주므로, 재귀적으로 호출 될때마다 계산하는것이 아닌

저장된 값에서 불러오기만 하면 되므로 빠르게 계산할 수 있게 된다.