[DP] 9461번 - 파도반 수열 - 실버3

[heerucan]

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

t = int(input())

p = [0] * 101
p[1] = 1
p[2] = 1
p[3] = 1
p[4] = 2
p[5] = 2

for i in range(6, 101):
    p[i] = p[i-1] + p[i-5]

for _ in range(t):
    n = int(input())
    print(p[n])

런타임에러 -> 인덱스 문제

• 왜 range가 101까지일까 -> 처음에 100으로 잡았다가 생각해보니 끝부분은 포함하지 않는 것을 깨달음
• 그렇다면 p 배열은 왜 101개가 필요할까?
  -> 문제 조건이 1<= N <= 100이다. 그래서 처음 값을 p[1]에 저장했는데 배열을 생각해보면 p[0]부터 시작한다. 결론적으로 100개의 배열을 만들면 처음 0번째에는 저장을 안해서 99개만 쓰는 거다.
  그렇기에 100개의 값을 메모하기 위해서는 101개가 필요하다.
• [0, 1, 1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]