[백준] 9095 1,2,3 더하기 - 파이썬(DP, 다이나믹 프로그래밍)

문제 출처

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

9095번: 1, 2, 3 더하기

 

DP 문제는 처음 접해봤는데 풀기 전 유튜브로 개념을 파악했다.

피보나치 문제처럼 같은 값을 계속 호출할 때 시간복잡도가 증가하므로 Memoization을 통해 이미 구한 값은 배열에 넣어두는 방식이다.

점화식을 세우는 것이 가장 중요하다.

DP 알고리즘이 사용되는 예시는 다음과 같다.

 

1. 큰 문제를 작은 문제로 나눌 수 있는 경우

2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일할 경우

 

밑 코드에서 주석 처리해놓은 점화식을 사용해야 한다.

이 문제는 계단을 올라가는 방법과 비슷하다.

첫번째 계단까지 올라갈 수 있는 방법이 1이므로 f(1) = 1

두번째 계단까지 올라갈 수 있는 방법은 1+1, 2 총 2개이므로 f(2) = 2

세번째 계단까지 올라갈 수 있는 방법은 1+1+1, 1+2, 2+1, 3 총 4개이므로 f(3) = 4 

 

점화식을 세운 이유는 사진과 같이 f(n)까지 올라갈 수 있는 경우의 수는 1,2,3만큼 움직일 수 있으므로 f(n-1),f(n-2),f(n-3)에서 올라가는 방법일 것이다. 마찬가지로 f(n+1)까지 올라갈 수 있는 경우의 수는 f(n),f(n-1),f(n-2)의 값의 합일 것이다.

그래서 초기 dp_arr 배열의 값을 0,1,2,4 로 지정했다. (index의 값과 계단 숫자를 같게하기 위해 0 추가)

 

import sys
# f(n) = f(n-1) + f(n-2) + f(n-3)
N = int(sys.stdin.readline())

def dp(n):
  if n == 1:
    return 1
  if n == 2:
    return 2
  if n == 3:
    return 4
  dp_arr = [0,1,2,4]

  for i in range(4,n+1):
    dp_arr.append(dp_arr[i-1] + dp_arr[i-2] + dp_arr[i-3])
  return dp_arr[n]

for i in range(N):
  num = int(sys.stdin.readline())
  print(dp(num))

# for i in range(N):
#   num = int(sys.stdin.readline())
#   res.append(dp(num))
# res2 = "\n".join(map(str,res))
# print(res2)