[n13699] 점화식

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

13699번: 점화식

매번 점화식을 재귀함수로 구하면

시간이 매우 오래걸려서

메모이제이션 방식을 사용하여 푼다.

 

처음엔, for문을 한 번만 돌리면 되는 줄 알았다.

n=3일경우

f(3)= f(0)*f(2) + f(1)*f(1) + f(2)*f(0)이니까

3번만 돌리면 되는 줄 알았는데

그게 아니었다...

 

array[1],array[2],array[3]... 

순서대로 값을 구해서 배열에 넣어야 점화식 문제를 풀 수 있다.

따라서 이중 for문을 사용해야한다.

 

array[0]의 값은 1로 고정시켜둔다.

 

i=1

array[1]=array[0]*array[0]

 

i=2

array[2]=array[0]*array[1]+array[1]*array[0]

 

i=3

array[3]=array[0]*array[2]+array[1]*array[1]+array[2]*array[0]

 

array[i]=array[j]*array[i-j-1]

 

# 점화식. 13699번
# 알고리즘 분류 : 다이나믹 프로그래밍, 메모이제이션
n = int(input())
array = [0 for _ in range(n + 1)]
array[0] = 1

for i in range(1, n + 1):
    for j in range(0, i, 1):
        array[i] += array[j] * array[i - j - 1]

print(array[n])

'''
array[1],array[2],array[3] .. 순차적으로 값을 구해서 array에 집어넣어야함.
이중 반복문 사용

'''