[🤷‍♀️ 백준] 9095번. 123 더하기

---

⛄

문제

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

---

⛄

답

def sum(n):
  l = [0,1,2,4] # 1,2,3 갑을 넣어줌

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

t = int(input()) # 테스트케이스
for _ in range(t): # 테스트케이스 수 대로 input 받기
  print(sum(int(input())))

 

계산할 수 있는 숫자는 1,2,3으로 구성된다고 했다.

n=1 일 때 > 1

n=2 일 때 1+1, 2 > 2

n=3 일 때 1+1+1, 2+1, 1+2, 3 > 4

n=4 일 때 1+1+1+1, 1+1+2, 2+1+1, 1+2+1, 1+1+2. 2+2, 3+1, 1+3 > 7

n=5 일 때 ... > 13

 

 

이걸 봤을 때 n=4일때

1로 시작하는 경우) 1+1+1+1, 1+2+1, 1+2+2, 1+3 > 4가지

2로 시작하는 경우) 2+2, 2+1+1 > 2가지

3로 시작하는 경우) 3+1 > 1가지

 

즉, n=1,2,3일 때의 합이 n=4와 같다는 것을 알 수 있다.

점화식은

n = n-1 + n-2 + n-3 

 

이걸 코드로 구성한다. 

---

알듯말듯한 다이나믹 프로그래밍😂