[BOJ] 2193: 이친수 (Python)

문제 링크

https://www.acmicpc.net/problem/2193

풀이 전략

Dynamic Programming

점화식을 세워 Bottom-up 방식으로 해결할 수 있는 간단한 동적계획법 문제입니다.

10844: 사과나무 문제와 비슷하게, 규칙을 찾으면 점화식을 쉽게 구할 수 있습니다.

구현

if __name__ == "__main__":
    n = int(input())
    dp = [(0, 0) for _ in range(91)]
    dp[1] = (0, 1)
    for i in range(2, n+1):
        dp[i] = (dp[i-1][0]+dp[i-1][1], dp[i-1][0])

    print(dp[n][0]+dp[n][1])