[백준] 9461_파도반 수열 (Python)

9461_파도반 수열 (Python)

0. 출처

• 유형 : DP (silver 3)
• 링크 : 9461번: 파도반 수열

1. 기록

• 22/06/30 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> DP
>> dp[i] = dp[i-2] + dp[i-3]

dp[1] = 1
dp[2] = 1
dp[3] = 1

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def dp_func(n):
    # fixme - 1. 테이블 정의
    dp = [0 for _ in range(101)]

    # fixme - 2. 초깃값 삽입
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1

    # fixme - 3. 테이블 채우기
    for i in range(4, n+1):
        dp[i] = dp[i] = dp[i-2] + dp[i-3]

    print(dp[n])

for _ in range(t):
    n = int(input())
    dp_func(n)

(4) 정리

문제를 완전히 이해하지 않아도 숫자 규칙을 찾으면 DP 문제임을 알고 쉽게 풀 수 있는 문제였다.

(5) 참고