[Python] 9461 - 파도반 수열

문제

9461번: 파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다.

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

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다.

• 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

• 각 테스트 케이스마다 P(N)을 출력한다.

---

풀이

그림을 잘 살펴보면 이전 삼각형의 길이를 더해서 새로운 삼각형의 길이를 알 수 있다.

따라서 DP 문제라는 것을 쉽게 알 수 있고 점화식도 쉽게 세울 수 있을 것이다.

굳이 세우지 않더라도 파도반 수열을 검색하면 위키에서 친절하게 점화식을 알려준다. 😆

Padovan sequence

In number theory, the Padovan sequence is the sequence of integers P( n) defined by the initial values and the recurrence relation The first few values of P( n) are 1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ...

https://en.wikipedia.org/wiki/Padovan_sequence

설명

• 여기 나오는 풀이는 그림을 보고 직관적으로 알 수 있는 점화식을 세운 것이기 때문에 위키에서와 다른 점화식을 가진다. (같은 결과를 가진다)

• 그림을 보고 다음 삼각형의 길이를 보면 직전 삼각형과 5번째 전 삼각형을 더한 것과 같기때문에

  $P[n] = P[n-1] + P[n-5]$

  이라는 점화식을 도출할 수 있다.

답

from sys import stdin

input = stdin.readline


def padovan_sequence(n):
    dp = [0, 1, 1, 1, 2, 2]
    for i in range(6, n + 1):
        dp.append(dp[i - 1] + dp[i - 5])
    return dp[n]


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        res = padovan_sequence(N)
        print(res)

Uploaded by Notion2Tistory v1.1.0