[algorithm] 백준 알고리즘 1005번 문제 정답코드

BOJ에서는 numpy를 사용할수 없어서, 아래와 같이 2차원 리스트를 생성하였다

http://hashcode.co.kr/questions/693/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4%EC%9D%80-%EC%96%B4%EB%96%BB%EA%B2%8C-%EC%93%B0%EB%82%98%EC%9A%94

아래는 코드.

recursion과 dynamic programming을 사용하였다

recursion depth는 n이 될 것이다

그림으로 표현하면 tree처럼 표현할 수 있다

#import numpy as np
#save = np.zeros((30, 30), np.uint32)
 
MAX = 30
save = [[0]*MAX for i in range(MAX)]
 
def bridge_cnt(n, m):
    if save[n][m] != 0:
        return save[n][m]
    
    for i in range(n-1, m): # n-1 ~ m-1
        save[n][m] += bridge_cnt(n-1, i)
    return save[n][m]
 
def main():
    for i in range(1, 30):
        save[1][i] = i
 
    T = int(input())
    for i in range(T):
        N, M = tuple(int(i) for i in input().split())
        print(bridge_cnt(N, M))
 
main()

언어는 python3가 아닌 pypy3를 선택했다