[백준/13699] 점화식 | 동적계획법 dp 개념(피보나치)| 이중포문의 활용 |

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

13699번: 점화식

---

[동적 계획법]

dp는 이전 문제들의 답을 메모해두는 알고리즘이다. 피보나치 수열과 같이 이전에 계산한 문제의 해가 계속 필요할 때 유용하다. 그래서 동적 계획법의 핵심은 "Memoization"이다. 메모리제이션은 이전에 계산한 값들을 저장해두고, 동일한 계산이 필요할 때 불러와서 계속 사용을 하는 기법

 

[피보나치 수열_동적계획법]

fibo(0) = 0
fibo(1) = 1
fibo(2) = fibo(1) + fibo(0)
fibo(3) = fibo(2) + fibo(1)
...
fibo(n) = fibo(n-1) + fibo(n-2)

 

def f(n) : 
    temp = 0
    c = [0, 1]
    for i in range(2, n+1) :
        temp += c[i-1] + c[i-2]
        c.append(temp)
        # print(c)
    return c
print(f(5))

위 코드를 실행하면 배열에 저장된 값들을 활용하여 피보나치 수열을 계산할 수 있다.

---

[최종코드]

n = int(input())
t = [1, 1, 2]

for i in range(3, n+1) : 
    ans = 0
    for j in range(i) : 
        ans += t[j] * t[i-j-1]
    t.append(ans)
    print(t)
print(t[n])

 

내가 처음에 생각 했던 코드는 ans += [t[i]*t[n-(i+1)]인데 이렇게 작성하면 점화식 인덱싱은 제대로 하지만, 배열에 저장되에 있는 값이 없기 때문에, 연산을 할 수가 없는 코드다. 😅

⭐️⭐️⭐️ 3>2>1>0 이렇게 변화하는 부분을 이중포문으로 작성할 수 있다는 걸 배웠다. ⭐️⭐️⭐️

---

Reference

되게 쉽고 자세하게 잘써두셔서 두고두고 보려고 같이 기록..

https://star7sss.tistory.com/157

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)