[BOJ/2193] 이친수 / DP , 피보나치 수열

# 0과 1로만 이루어진 수

n = int(input())
# n 자리 이친수의 개수

dp = [0]*(n+1)
dp[1] = 1
#이친수는 0으로 시작할 수 없음 (단한가지)

if n >= 2:
    dp[2] = 1
# 10 만 가능함 (단한가지)

for i in range(3,n+1):
    # 3자리부터 n자리까지의 이친수 개수를 구할 때까지 반복
    dp[i] = dp[i-1] + dp[i-2]
    # 전형적인 피보나치 수열과 동일한 점화식
print(dp[n])

 

이친수 조건:

1. 0으로 시작 ❌
2. 1이 두 번 연속 나오면 안 됨 (11 ❌)
3. 이진수만 사용 가능 (0 또는 1)

즉, 이친수는 맨 끝이 1이면 반드시 그 앞은 0 이어야 함

 

이 문제를 DP로 풀이하는 이유: 어떤 자릿수까지 올 때 그 이전 자릿수의 패턴만 기억하면 몇 개가 가능한지 누적해서 계산할 수 있음

 

dp[n] = dp[n-1] + dp[n-2]

이 점화식을 쓰기 위해선 반드시 dp[1]과 dp[2]를 정확하게 초기화해야
dp[3], dp[4] ... 등을 올바르게 쌓아갈 수 있음