연습장/백준(BOJ) 문제풀이
[백준 2193] 이친수 with Python
Tesseractjh
2021. 4. 22. 21:39
문제 링크
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
풀이
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이다.