[백준] 9461번 - 파도반 수열 (파이썬)

 

 

" 백준 9461번 파도반 수열 문제 파이썬 "

 

9461번: 파도반 수열

 

9461번

 

 

" 💡 문제 해결 아이디어 "

 

이 문제는 주어진 수열 문제와 초기 값을 통하여 P(N) 값을 구해내는 문제이다.

 

이 문제는 기존 값을 통하여 이후의 값을 유추할 수 있기 때문에 DP문제로 분류할 수 있다.

 

 

점화식 찾기

 

2(p[5]) = 1(p[3]) + 1(p[2])

3(p[6]) = 2(p[4]) + 1(p[3])

4(p[7]) = 2(p[5]) + 2(p[4])

...

9(p[10]) = 5(p[8]) + 4(p[7])

 

미리 주어진 값을 통해 도출해낸 위 값을 통해 유추할 수 있듯이

이번 문제는 문제에 주어진 초기값을 통해 p[n] = p[n-2] + p[n-3] 이라는 점화식으로 해결할 수 있음을 확인할 수 있었다.

 

다음으로 코드를 확인해보자.

 

 

코드

# 초기에 주어진 값
# P = [1, 1, 1, 2, 2, 3, 4, 5, 7, 9]

# 여기서 p[n] = p[n-2]+p[n-3] 이라는 규칙을 찾을 수 있음

t = int(input()) # Test Case 횟수 입력
dp = [-1 for _ in range(101)] # n의 범위가 1 <= n <= 100 이기 때문에 0~100까지의 값 저장공간을 -1로 초기화하여 생성한다.
# 주어진 초기값 세팅
dp[0] = 0 
dp[1] = 1
dp[2] = 1


for i in range(t):
    n = int(input())
    if dp[n] != -1: # dp[n]의 값이 -1이 아니면 이미 구해진 값이기 때문에 그대로 출력
        print(dp[n])
    elif dp[n] == -1: # dp[n]의 값이 -1이면 아직 구해지지 않은 값이므로 구하는 과정 수행후 출력
        for j in range(3, n+1):
            if dp[j] != -1: # 이미 구해진 값이면 skip
                continue
            dp[j] = dp[j-3]+dp[j-2] # skip되지 않은 경우 구해지지 않은 값이므로 "규칙을 통한 값 계산"
        print(dp[n])