[백준, 9461번] 파도반 수열

• 단순히 문제에 나와있는 P(10)까지의 규칙을 확인해보면
  • 해당 위치의 세 번째와 두 번째 위치 전의 값을 더한 값이 현재 위치의 값이 되기에
  • dp를 활용해서 풀었으며, li를 초기화하지 않고 전역에 놔두며 계속 추가함으로써
  • n-1번째 값이 현재 li에 있다면 바로 출력해 불필요한 시간을 줄이도록 하는 코드를 작성.

li = [1, 1, 1]+[0]*97
for i in range(int(input())):
    n = int(input())
    if li[n-1] != 0: 
        print(li[n-1])
        continue
    for j in range(3, n):
        li[j] = li[j-3]+li[j-2]
    print(li[j])