백준 9461번 - 파도반 수열

노트에 그려가면서 풀면 왜 문제에서 첫 10개의 숫자를 줬는지 대충 감이 온다. 삼각형을 그려보면 N번째 삼각형의 한 변의 길이는 바로 이전 삼각형의 변의 길이에 5번째 전(한 바퀴 돌고 난 뒤) 삼각형의 변의 길이를 더한 값과 같다는 것을 알 수 있다. 그러므로 점화식은 P(N) = P(N-5) + P(N-1)이다. 이를 이용해서 재귀 함수를 사용하지 않고 반복문을 사용해서 배열을 append 해주면 된다.

 

##변수 선언 부분##
p = [0, 1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

##메인 함수 부분##
if __name__ == "__main__":
    T = int(input())
    for i in range(T):
        N = int(input())
        for j in range(11,N+1):
            tmp = p[j-5] + p[j-1] #문제의 점화식
            p.append(tmp)
        print(p[N])
        for j in range(N - 10): #반드시 초기화를 해줘야한다.
            p.pop()

어렵지 않았지만 테스트 케이스마다 배열값을 초기화해주는 것을 까먹어서 틀렸던 문제다. 테스트 케이스가 주어지는 문제에서는 초기화를 잊지 말자