9461

날짜 : 2022. 11. 18

사용 언어 : python

 

문제

 

 

코드

import sys

a = [1, 1, 1, 2, 2, 3]
for i in range(5, 102):
    t = a[i] + a[i-4]
    a.append(t)
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    print(a[n-1])
#print(a)

 

 

풀이

- 해당 그림을 보았을 때 2 = 1 + 1, 3 = 1 + 2, 4 = 1 + 3 ... 이런식으로 전개되었고 이전에 쓰였던 변들의 길이가 규칙적으로 사용되었다는 점을 포착했다.

- 그래서 a[i] = a[i-1] + a[i-5] 라는 점화식이 도출되었고 이를통해 문제를 해결할 수 있었다.

 

 

알게된 점

- 

 

 

참고 사이트

-