스파르탄 365 4주차 (1) 파도반 수열

4주차

백준 9461번 랜선 자르기

문제링크 : https://www.acmicpc.net/problem/9461

💡 풀이 전 계획과 생각

피보나치 수열의 응용이구나~!

• 예제를 써보다가 보이는 규칙으로 점화식을 세우자
  = P[i] = P[i-3] + P[i-2]

💡 풀이

import sys
input = sys.stdin.readline

test_case = int(input())

for _ in range(test_case):
    N = int(input())
    P = [0, 1, 1, 1]

    for i in range(4, N+1):
        P.append(P[i-3] + P[i-2])

    print(P[-1])

막혔던 점과 고민

🧐 고민했던 점

1, 2, 3번째에 1을 어떻게 넣을까
! 그냥 P배열에 미리 넣고 시작하자, 변함없는 값이니까

👏🏻 알게된 개념과 소감

자신감이 생겼다 :]