[ 2023-03-21 ⛄️ TIL ]

백준 2193번

문제를 직접 풀어보니 규칙이 존재하는것을 확인하였습니다.

i번째의 이친수의 갯수가 i-1과 i-2의 이친수의 갯수를 더한 수와 같다는 것입니다.

이걸 식으로 나타내면 n[i] = n[i-1] + n[i-2]

dp를 이용해서 풀면 빠를 것 같아

import sys

input = sys.stdin.readline

n = int(input())
dp = [1, 1, 2] + [0 for _ in range(n)]

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

print(dp[n-1])