[BOJ] 2193번 - 이친수

---

문제설명

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

2193번: 이친수

사고과정

• 경우의 수를 n = 7까지 나열해보고 패턴을 못찾는 듯 했으나..! 간신히 찾았다! 매우 간단한 점화식이었다. $dp[i] = dp[i-1] + dp[i-2]$ 
• 처음에 인덱스 에러가 발생했는데, n = 1일 때의 조건을 처리해주어야 한다. DP에서는 입력이 1일 때 처리를 해주는 조건을 자주 붙이는 듯 하다.
• 1,2,3 더하기 문제랑 동일한 점화식이었다. 아쉽다고 한다면 조금만 더 패턴을 빨리 찾았으면 어땠을까..!

풀이

n = int(input())
if n == 1:
    print(1)
else:
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 1

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

    print(dp[n])