[백준] 9095번-(Python 파이썬) - DP

문제링크 : https://www.acmicpc.net/problem/9095

이번에도 다이나믹 프로그래밍을 이용하는 문제이다.
dp문제는 규칙만 잘찾으면 코드가 매우 짧게 나온다는 걸 느꼈다.
쉬운문제들은 규칙이 쉽게 보여 금방 풀리는 감이 없지않아 있는 것 같다.

import sys
input = sys.stdin.readline

dp = {
  1 : 1,
  2 : 2,
  3 : 4
}

def f(n):
  if n not in dp: 
    dp[n] = f(n-1) + f(n-2) + f(n-3)
  return dp[n]

t = int(input())

for _ in range(t):
  n = int(input())
  print(f(n))

첨엔 그냥 n이 4일때, 5일때, 6일때까지 순수하게 하나하나 값을 구해
그 전에 값들과의 규칙을 찾다보니 이유는 모르지만
앞에 3개의 값을 더한값이 결과값이라는 것을 알게 되었다.
제출하고 나서 이유가 궁금해 찾아보니 다른분이 올려두신 글에서 이유를 알 수 있게
되었다.

참조한 분의 글 링크 : https://jyami.tistory.com/15

내글보다 훨씬 설명도 더 잘되어있고 읽어보면 확 이해가 된다.

이분글에서 가져온 이미지를 보면 알 수 있듯이 1을 더했을때, 2를 더했을 때, 3을 더했을 때
현재의 수가 나오는, 각각의 이전 조합의 경우의 수를 더하면 답이 나오게 된다.

a(n)을 구하기 위해선
1 + a(n-1)
2 + a(n-2)
3 + a(n-3)
일 때가 a(n)이 나오는 경우의 수인 것이다.

아직은 많이 서툴지만 하루빨리 성장해 높은 난이도의 문제들도 풀 수 있는 날이
오도록 노력해야겠다.