[백준] 9461번: 파도반 수열 / 파이썬

문제 링크

---

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

풀이 코드

---

for i in range(int(input())):
    p = [1,1,1]     #배열 앞부분은 미리 선언
    n = int(input())
    for j in range(n-3):    
        p.append(p[j]+p[j+1])   #배열에 p[n-2] + p[n-3]의 값을 더해줌
    print(p[-1])    #마지막 값 출력

코드 해석

---

점화식을 찾으면 매우 쉽게 풀 수 있다. 

점화식은 다음과 같다.

p(n) = p(n−2) + p(n−3)

만약 n이 3 이하라면 p(n)은 1

 

for문으로 t번 반복한다.

배열 앞 세 자리는 식을 위하여 미리 선언해둔다.

수를 받은 후

배열에 p[n-2] + p[n-3]의 값을 더해준다.

n의 끝까지 반복하면 끝.

마지막으로 배열의 마지막 값을 출력하면 된다.

 

점화식만 찾는다면 레이팅에 비하여 매우 쉬운 난이도다.

난이도: ★☆☆☆☆