[백준알고리즘] 9461번: 파도반 수열 -Python

[백준알고리즘] 9461번: 파도반 수열 -Python

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

9461번: 파도반 수열

초기에 5번째 삼각형까지는 길이를 직접 넣어주었다.

 

그리고 그림에서의 규칙을 찾아 side[i] = side[i-1] + side[i-5] 를 통해 구했다. DP를 사용하면 간단하게 해결할 수 있었다.

 

이전에도 풀었던 문제인데, 이전에는 규칙을 side[i] = side[i-2] + side[i-3] 으로 풀었었다. 내가 풀었던 건데 어떻게 이런 규칙을 찾았는지 모르겠다. ㅋㅋㅋㅋㅋ 어쨌든 되는 걸 보고 신기했다. 다른 분들의 코드를 봐도 다 제각각으로 규칙을 찾아서 풀었다..

 

코드에서는 side로 안하고 table로 리스트 이름을 잡았다.

import sys

testcase = int(sys.stdin.readline())
table = [0, 1, 1, 1, 2, 2]

for _ in range(testcase):
    N = int(sys.stdin.readline())
    length = len(table) - 1

    if N > length:
        for t in range(length+1, N+1):
            table.append(table[t-1] + table[t-5])

    sys.stdout.write(str(table[N]) + "\n")

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다