[백준 2193] 이친수 with Python

문제 링크

www.acmicpc.net/problem/2193

2193번: 이친수

풀이

import sys

n = int(sys.stdin.readline())
dp = [0]*91
dp[1], dp[2] = 1, 1
for i in range(3, n+1):
    dp[i] = sum(dp[1:i-1]) + 1
print(dp[n])

이친수는 0으로 시작할 수 없으므로 맨 앞자리 수는 반드시 1이다. 그리고 1이 두 번 연속 올 수 없으므로, 그 다음 자리수는 반드시 0이다. 이렇게 앞 두자리가 10으로 고정되어 있으므로, 그 뒤에 오는 숫자들은 1~N-2까지의 경우가 다시 반복된다. 이를 표로 나타내면 아래와 같다.

 

N = 1	N = 2	N = 3	N = 4	N = 5
1	10	100 101	1000 1001 1010	10000 10001 10010 10100 10101

N >= 3인 경우부터 앞의 10을 제외한 모든 자릿수가 0인 경우 하나와 1~N-2까지의 경우가 모두 나타난다. 따라서, 이친수의 개수를 dp[N]이라고 할 때 N >= 3인 경우에 dp[N] = dp[1] + dp[2] + ... + dp[n-3] + dp[n-2] + 1이다.