Algorithm/BOJ
[백준] 9461 파도반 수열 (파이썬 python)
YOONJELLY
2022. 1. 19. 18:28
문제 링크
https://www.acmicpc.net/problem/9461
9461번: 파도반 수열
오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의
www.acmicpc.net
문제
문제 풀이
문제에서 주어진 예제만으로 점화식이 쉽게 구해진 문제였다.
P[1], P[2], P[3]까지는 모두 1의 값을 가지고
n이 4부터 100까지의 값일 경우 P[n] = p[n - 3] + p[n - 2] 의 점화식을 가진다.
즉, 수열에서 2개 전, 3개 전 숫자끼리 더한 값이 현재 값이다.
p = [0 for i in range(101)]
p[1] = 1
p[2] = 1
p[3] = 1
for i in range(3, 101):
p[i] = p[i - 3] + p[i - 2]
t = int(input())
for i in range(t):
n = int(input())
print(p[n])