오늘의 문제
https://www.acmicpc.net/problem/9461
포인트 쳌쳌
- 1904 01타일 문제처럼 점화식 규칙을 찾으면 쉽게 풀리는 문제이다.
이 문제에서 찾은 규칙을 점화식으로 나타내면P[N] = P[N-1] + P[N-5]
처럼 나타낼 수 있다. 언뜻 피보나치 수열과 비슷해보인다. 따라서, 메모이제이션을 이용하여 P[N]값을 구하기로 했다. - result라는 새 리스트에 테스트케이스의 입력값(n)들을 차례차례 저장한다.
- 입력값 n의 범위는 1이상
100이하
라는 점을 이용하여 사이즈 101의 리스트를 생성한다.(fibo)
100이 아닌 101인 이유는 인덱스 0번을 사용하지 않기 위해서이다. - 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])