백준 9095번 파이썬 _ 1,2,3 더하기

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

문제유형 : DP

문제해설 :

 

<규칙>

1 = (1)

2 = (1 + 1), (2)

3 = (1 + 1 + 1), (1 + 2), (2 + 1), (3)

4 = (1 + 1 + 1 + 1), (1 + 1 + 2), (1 + 2 + 1), (1 + 3), (2 + 1 + 1), (2 + 2), (3 + 1)

 

핵심 : 점화식찾기

F(n) = F(n-1) + F(n-2) + F(n-3) (n>3) 을 찾으면 쉽게 풀리는 문제였다.

test_case=int(input())

input_list=[int(input()) for _ in range(test_case)]

dp=[1,2,4]

for i in range(3,max(input_list)):
    dp.append(dp[i-1]+dp[i-2]+dp[i-3])

for i in input_list:
    print(dp[i-1])

---

처음에 무슨 팩토리얼로 생각해서 풀려다가;; 뭔가 점점더 산으로 가는 느낌을 받아 이건 아니군 생각함

처음 볼때부터 DP인거같다는 생각이 들긴했는데 딱히 방법이 딱 안떠올라서 다른방법으로 가다가 넘 안풀려서 다시 DP구나했다.

그래서 이문제는 규칙성을 찾으면 쉽게 풀수 있는 문젠데 쉽게 생각나진 않았다... 줅

아직 알고리즘 문제를 많이 안풀어봐서 이런 유형의 문제를 처음봐서 그랬던것같기도하다

DP인거같은데 DP로 어떻게 해결할지 모르겠다면 일단 3-4 정도 까지 규칙성 구해본다음 점화식 찾을수있나 확인해보자.