문제

' 9095번 1, 2, 3 더하기 '
https://www.acmicpc.net/problem/9095

Check point

📌 동적 계획 (DP) / Dynamic Programming

💡 DP란?

• 입력 크기가 작은 부분 문제들을 모두 해결하여 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘
  
  
• 재귀와 방식이 매우 유사하나 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있는 재귀의 문제를 해결하기 위해 DP를 사용한다.
  => 즉, 분할된 하위 문제가 동일한 반복이 일어나면 DP를 사용한다.

💡 DP의 구현 방식

• recursive 방식 ( 재귀 ) : fib1()
• iterative 방식 ( 반복 ) : fib2()
  
  
• memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 구현한 것이 성능면에서 효율적
  재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문

📌 풀이 접근 방법

• 정수 4를 1, 2, 3 의 합으로 나타내는 방법 총 7가지가 정수 1 , 정수 2, 정수 3 을 각각 1, 2, 3 의 합으로 나타내는 방법과의 연관성을 찾는다.
• 정수 n에 따라서 dp의 항목을 나누는 방법을 찾는다.

코드

python

def find(n):
    dp = [0] * (n + 1)
    dp[1] = 1  # 1
    if n == 2:
        dp[2] = 2  # 2 / 1+1
    if n == 3:
        dp[2] = 2
        dp[3] = 4  # 3/ 1+2 /1+1+1/ 2+1
    if n > 3:
        dp[2] = 2
        dp[3] = 4
        for i in range(4, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] # dp[4] = 1 + 2 + 4 = 7
    return dp[n]


T = int(input())
for i in range(T):
    n = int(input())
    print(find(n))