[백준] 9461. 파도반 수열 - 파이썬 풀이

백준 파도반 수열

풀이

• 백준 사이트 특성상 알고리즘의 분류가 되어 있어 DP 문제라는 것을 알 수 있지만 실전같은 경우는 어떻게 DP 문제라는 것을 유추할 수 있을까?
  • 위의 문제에서 제시한 예시를 보면 이 전의 연산 결과에 따라서 다음의 연산 결과를 저장한다.
  • 고로 작은 것을 통해 큰 것의 최적해를 찾는 것이기 때문에 DP를 사용하면 된다는 것을 유추할 수 있다.
  • 또한 입력 N의 범위가 1 <= N <= 100 이다. 큰 숫자가 주어진 것이 아니기 때문에 2중 for loop까지는 적용할 수 있을 것을 생각 해 볼 수 있다.
• 이제 문제의 규칙을 알아보자
  • 문제에서 주어진 예시를 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 로 주어졌다.
  • 자세히 보면 무언가 1 + 1 값이 뒤의 2가 되는 것 같고 2 + 2의 값이 뒤의 4가 되는 것 같고 4 + 5의 값이 뒤의 9의 값이 되는 것 같다.
  • 이를 점화식으로 추론해보면 dp[i] + dp[i+1] = dp[i+3] 값이 된다는 것을 확인할 수 있다.
  • 이제 이를 코드로 구현해주면 된다.

코드

import sys  
sys.stdin = open("9461_파도반수열_input.txt", "rt")  

t = int(sys.stdin.readline())  

for i in range(t):  
    n = int(sys.stdin.readline())  
    dp = [0] * 101  
    dp[1], dp[2], dp[3] = 1, 1, 1  

    for j in range(1, n - 2):  
        dp[j + 3] = dp[j] + dp[j + 1]  

    print(dp[n])

• 주의할 점으로는 i + 3 까지를 연산하기 때문에 n - 2까지만 반복문을 수행하면 답을 얻을 수 있다. 이를 간과하고 범위를 정하면 IndexError가 발생한다.