[Python Algorithm] 이친수 BOJ #2193

문제

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

2193번: 이친수

 

내 문제 풀이

n = int(input())

if n == 1: print(1)
elif n == 2: print(1)
else:
    result = [1, 1]  # n이 0일 때, 1일 때를 미리 저장
    for i in range(2, n):
        result.append(result[i-2] + result[i-1])
    print(result[-1])

👉 DP 문제로, 점화식 사용해주면 됨 !

p(n) = p(n-2) + p(n-1) 의 점화식을 가지고 있으므로, 이에 맞게 풀어주었다.

(직접 구해보면 N이 6일 때 8개, N이 7일 때 13개, N이 8일 때 21개의 경우를 가진다.) 

 

💡 피드백

• 전형적인 점화식 문제였고, 쉽게 유추해서 풀 수 있었다.