백준 1904 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍

  • 설명

    • 동적 프로그래밍 문제를 풀기 위해서는 점화식(인접한 항들 사이의 관계식)을 세워야 한다.

      스크린샷 2020-10-30 오후 7 19 58

    • D[i] = 수열의 길이가 i일 때의 경우에 수

    • D[i] = D[i-1] + D[i-2]

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    n = int(input())

    dp = [0] * 1000001
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n+1)
        dp[i] = (dp[i - 2] + dp[i - 1]) % 15746

    print(d[[n]])