백준 9507번 - Generations of Tribbles

 

1. 문제 난이도

---

2. 문제설명

피보나치 수열이 변형된 듯한 수열을 소개하고

이 수열의 N번째 항을 구하는 문제이다.

 

<INPUT>

첫 줄: 테스트케이스의 개수 t

다음 t줄: n

 

<OUTPUT>

각 input n에 대해 수열의 n째 값

---

3. 아이디어

다른 수열문제처럼 DP를 활용하는 것은 쉽게 생각할 수 있다.

그러나 입력의 개수가 많기 때문에 나는

입력 받은 값들 중 가장 큰 값을 구한 뒤,

그 값까지의 수열을 먼저 구했다.

그 후 각 입력에 맞는 수열의 값을 출력했다.

---

4. 구현

nlist=[1,1,2,4]

def func(n):
    return nlist[n-1]+nlist[n-2]+nlist[n-3]+nlist[n-4]


inputlist=[]
t=int(input())
for i in range(t):
    inputlist.append(int(input()))

for i in range(4,max(inputlist)+1):
    nlist.append(func(i))

for i in inputlist:
    print(nlist[i])

댓글, 오류지적 모두 감사합니다