이친수 백준 2193번 DP

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

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

• 이친수는 0으로 시작하지 않는다.
• 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
• 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

---

간단하게 5자리 수까지 만들어보면 점화식이 나옵니다.

1
10
101, 100
1010, 1001, 1000
10100,10010,10001,10101,10000

바로 dp[i] = dp[i-1] + dp[i-2]가 나오네요

num = int(input())
dp = [0]*92
dp[1] = 1
dp[2] = 1
for i in range(3,num+1):
    dp[i] = dp[i-1] + dp[i-2]
print(dp[num])

주어진 조건에서 N의 범위가 90이하이기 때문에 반복문을 입력값이 아니라 90번을 돌려도 사실상 속도는 똑같이 나옵니다.