[DP] 9095번 - 1, 2, 3 더하기 - 실버3

[heerucan]

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

t = int(input())

d = [0] * 11
d[1] = 1
d[2] = 2
d[3] = 4

for i in range(4, 11):
    d[i] =  d[i-1] + d[i-2] + d[i-3]

for _ in range(t):
    n = int(input())
    print(d[n])

생각

• d[n]에 저장될 값은 n을 1,2,3의 합으로 나타내는 방법의 수다.
• 그럼 생각해보면 어떤 값인 n을 만들기 위해서 가장 끝자리에 1/2/3 중 하나가 올 것이다.
  n = x + x + .... + 1 -> 이 경우에 d[n-1] + 1
  n = x + x + .... + 2 -> 이 경우에 d[n-2] + 2
  n = x + x + .... + 3 -> 이 경우에 d[n-3] + 3

글서 점화식이 d[i] = d[i-1] + d[i-2] + d[i-3] 이렇게 된다.

• 문제 조건이 11보다 작은 양수기에 메모할 배열 d는 11개로 공간을 만들고
• 첫 시작을 d[1]로 하기에 11로 값을 잡는 것이다.
• range도 마찬가지로 4 ~ 10을 해야 하기에 11로 끝값을 준 것이다.