9095

날짜 : 2022. 11. 02

사용 언어 : python

 

문제

 

 

코드

import sys

t = int(sys.stdin.readline())
arr = [0] * 12
arr[1] = 1
arr[2] = 2
arr[3] = 4
for i in range(4, len(arr)):
    arr[i] = arr[i-1] + arr[i-2] + arr[i-3]

for _ in range(t):
    n = int(sys.stdin.readline())
    print(arr[n])

 

 

알게된 점

- 해당 문제에서 4를 표현하기 위해서는 3 + 1, 2 + 2, 1 + 3. 즉, 3가지 경우로 표현할 수 있다.

- 이를 점화식으로 정리하면 a[n] = a[n-1] + a[n-2] + a[n-3]이라는 식으로 정리할 수 있다.

- 또한 반복문을 통해 재귀를 없애야 한다는 점, 최대  n값이 11이라는 점을 이용해 해당 리스트를 미리 돌려 값을 도출한 후 입력한 값에 따라 아웃풋을 출력하는 방식으로 문제를 해결했다.

 

참고 사이트

-