[Python] 백준 #9095- 1,2,3 더하기

문제

---

9095번: 1, 2, 3 더하기

코드

---

My answer

a=[0,1,2,4]+[0]*8

n=int(input())
for i in range(4,12):
    a[i]=a[i-1]+a[i-2]+a[i-3]
for i in range(n):
    tmp=int(input())
    print(a[tmp])

Another answer

dp=[1,2,4]
for i in range(4,12): 
    dp.append(sum(dp[-3:]))
for _ in range(int(input())): 
    print(dp[int(input())-1])

 

풀이

---

우선 맨 처음에 문제를 잘못 이해해서 한참을 헤맸다. 우선 dp문제인만큼 규칙을 알아내려고 했는데 아무리 생각해도 규칙이 안나왔다. 알고보니 문제를 잘 안읽어서였다.. 결과적으로 점화식은 n>=4일때, a[n]=a[n-1]+a[n-2]+a[n-3] 이 나온다. 이 식을 알아내고도 못풀었던 이유는 나는 a[1]=0,a[2]=1(11),a[3]=3(111,12,21)으로 생각했기 때문이다. 문제를 잘 읽어보면 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 고 써있다. 나는 맨처음에 문제가 1,2,3 더하기 라고 써져있어서 수 한개로 이루어진건 안된다고 생각했다. 이거 때문에 규칙을 파악못했었고 규칙을 찾은다음에도 계속 틀렸었다.. 테스트 케이스 다 맞는데 틀리는분은 다시 한번 보길 바란다