[Algorithm]9461 파도반 수열 By Python3

오늘의 문제

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

포인트 쳌쳌

1. 1904 01타일 문제처럼 점화식 규칙을 찾으면 쉽게 풀리는 문제이다.
   이 문제에서 찾은 규칙을 점화식으로 나타내면 P[N] = P[N-1] + P[N-5] 처럼 나타낼 수 있다. 언뜻 피보나치 수열과 비슷해보인다. 따라서, 메모이제이션을 이용하여 P[N]값을 구하기로 했다.
2. result라는 새 리스트에 테스트케이스의 입력값(n)들을 차례차례 저장한다.
3. 입력값 n의 범위는 1이상 100이하 라는 점을 이용하여 사이즈 101의 리스트를 생성한다.(fibo)
   100이 아닌 101인 이유는 인덱스 0번을 사용하지 않기 위해서이다.
4. for문을 통해 수열 값들을 생성하되, 입력값의 최대값을 초과하는 인덱스에 대해서는 접근하지 않았다.

풀이 코드

t = int(input())
result = [] #테스트 케이스 n들을 저장할 변수

for i in range(t):
    n = int(input())
    result.append(n)
    
fibo = [0]*101 #n의 값이 100 이하 이므로
fibo[1], fibo[2], fibo[3] = 1,1,1
fibo[4], fibo[5] = 2, 2

for i in range(6, max(result)+1):
    fibo[i] = fibo[i-1]+fibo[i-5]
#print(fibo)

for item in result:
    print(fibo[item])

채점 결과