[BOJ 9461] 파도반 수열(Python)

문제링크

파도반 수열

풀이 전 계획 및 생각

문제를 읽으면서 규칙에 따라서 수열을 만들 수 있다는 생각을 했다.

그림을 보니 7번째 삼각형부터는 i번째 삼각형의 한 변의 길이는 i-1번째 삼각형과 i-5번째 삼각형의 한 변의 길이의 합과 같다는 것을 발견했다. 6번째 삼각형까지는 문제에서 주어졌기 때문에, 주어진 값으로 초기화를 했고, overflow를 방지하기위해서 넉넉하게 배열을 만들어줬다.
그 후 100번째 삼각형까지의 길이를 구했다.
그 후 test_case만큼 n을 입력받고 출력하도록 구현했다.

풀이

import sys
pado = [0,1,1,1,2,2,3] + [0]*100

test_case = int(sys.stdin.readline())
for i in range(7,102):
    pado[i] = pado[i-1] + pado[i-5]
for t in range(test_case):
    n = int(sys.stdin.readline())
    print(pado[n])

풀이하면서 막혔던 점과 고민했던 점

크게 막히거나 고민했던 점은 없다.

풀이 후 알게된 개념과 소감

DP문제는 수학적 귀납법처럼 명제를 세우고 그게 성립하는지 확인하고 그대로 구현하면 된다는 생각을 했다. 그래서 참 재밌는 것 같다.