📖Problem

9461번: 파도반 수열

🔍Institution

문제에서 “P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.”라고 말한 부분을 토대로 점화식을 세워 풀면 되겠다는 생각이 들었다. 점화식을 세우기 위해서는 규칙을 찾아야 한다.

Untitled

그래서 아래와 같이 그려보면서 규칙성을 찾았다.

IMG_1886.png

내가 찾은 점화식은 $P(N) = P(N-3)+P(N-2)$ 이다. 점화식에서 최소로 필요한 값인 P(N-3)을 만족하기 위해서는 반복문을 시작할 때의 값은 4부터 시작해야 하며, 이를 위해서는 P(1)~P(3) 까지는 미리 값이 1로 초기화되어 있어야 한다는 것을 알 수 있다

🔍Approach

🚩플로우

  1. 테스트케이스의 수, T를 입력받는다.
  2. dp테이블, dp를 초기화한다. 문제에서 최대값이 100이고, 사용하는 값은 1부터 시작하므로 101사이즈로, 그리고 미리 설정해두어야 하는 P(1)~P(3)의 값이 1이므로 [1] * 101로 초기화한다.
  3. T만큼 반복하며 테스트케이스 값, p_n을 입력받는다.
  4. dp를 시작하는 반복문을 넣는다. 이는 4부터 p_n까지 반복하며, 위에서 세운 점화식 dp[i] = dp[i-3]+dp[i-2] 를 수행한다.
  5. 입력한 테스트케이스의 결과값을 출력한다.

🚩My submission

import sys
input = sys.stdin.readline

t = int(input()) #테스트케이스의 수
dp = [1] * 101
for __ in range(t): # 테스트케이스 수만큼 반복
    p_n = int(input()) # 테스트케이스 입력
    for i in range(4, p_n+1): #4부터 시작
        dp[i] = dp[i-3] + dp[i-2] # 점화식
    print(dp[p_n])

Untitled

🚩Others submission