[BOJ_2193] 이친수

n = int(input())

dp = [0 for _ in range(91)]

dp[1] = 1
dp[2] = 1

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

print(dp[n])

0으로 시작하지 않으면서 11을 부분 문자열로 갖지 않는 수를 이친수라 합니다.

일단 낮은 차수의 항들을 수동으로 구해줍시다.

1	2	3	4
1	10	100 101	1000 1010 1001

 

첫번째 두번째 항을 주목해 보면

한자리 수 이친수에 01을 붙이고

두자리 수 이친수에 0을 붙이면

101, 100으로 세자리 수의 이친수가 되는 것을 발견할 수 있습니다. 

 

두자리 수 이친수에다가 01을 붙이고

세자리 수 이친수에 0을 붙이면

1001, 1000, 1010으로 네자리 수의 이친수가 만들어 집니다.

 

점화식을 구해보면

f(n) = f(n-2) + f(n-1)

입니다. 또 피보나치 수열이네요.

 

www.acmicpc.net/problem/2193

2193번: 이친수