BOJ - 1309

백준 문제 링크
동물원

❓접근법

1. N이 1일 때 경우의 수 3가지
   (0 - 1가지, 1 - 2가지)
   N이 2일 때 경우의 수 7가지
   (0 - 1가지, 1 - 4가지, 2 - 2가지)
   N이 3일 때 경우의 수 17가지
   (0 - 1가지, 1 - 6가지, 2 - 8가지, 3 - 2가지)
   점화식은 DP[i] = DP[i-1] * 2 + DP[i-2]로 알 수 있음.
2. 점화식을 이용해 DP에 저장 후 반환하면 끝!

👌🏻코드

N = int(input())

if N == 1:
    print(3)
    
else:
    dp = [0] * (N+1)
    dp[1] = 3
    dp[2] = 7
    
    for i in range(3, N+1):
        dp[i] = dp[i-1] * 2 + dp[i-2]
        
    print(dp[N])