[백준/9095/파이썬] 1,2,3 더하기 - DP

---

소스코드

T = int(input())

for i in range (T):

  n = int(input())

  dp = [0]*(n+1)

  if n == 1 :

        print(1)

  elif n == 2 :

      print(2)

  elif n == 3 :

      print(4)

  else :

      dp[1] = 1

      dp[2] = 2

      dp[3] = 4

      for j in range(4,n+1) :

          dp[j] = dp[j-1] + dp[j-2] + dp[j-3]

      print(dp[n])

---

알고리즘

현재 자료구조 과목만 수강을 해서 알고리즘에 대해 생소한 부분이 있다면 바로 DP인것 같아요.

DP란 Dynamic Programming으로 동적프로그래밍이라고 하는데 계산값을 선언된 배열에 넣어줌으로서 많은 연산을 줄여주는 프로그래밍 기법입니다. 예를들어 피보나치 수열에서 213446번째를 구하려면 213445!번 계산을 해야 구하고 하지만 리스트에 213444번째와 213445번째가 있다면 금방 구할 수 있겠죠?
아무튼 이번 문제는 DP라는 기법을 모르고 풀었더라면 엄청난 계산의 양이 필요할 수도 있는 문제였어요.

1 -> 1 1개

2 -> 1+1, 2 2개

3 -> 1+1+1, 1+2, 2+1, 3 4개

4 -> 7개

5 -> 13개

6 -> 24개

7 -> 44개

...

f(n) = f(n-1) +f(n-2)+ f(n-3)

이런 점화식을 찾을 수가 있네요

문제 자체는 쉬워보였지만 좋은 알고리즘을 짜는건 쉽지 않다는것을 깨닫는 하루입니다..