Algorithm PS/BOJ
[BOJ] 2193 / 이친수 / Python
migrationArc
2021. 5. 11. 18:35
[BOJ] 2193 / 이친수 / Python
https://www.acmicpc.net/problem/2193
2193번: 이친수
0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않
www.acmicpc.net
풀이
경우의 수를 구하여 나열해 보았다.
N = 1 -> 1
N = 2 -> 10
N = 3 -> 100 101
N = 4 -> 1000 1001 1010
N = 5 -> 10000 10001 10010 10100 10101
N = 6 -> 100000 100001 100010 100101 100100 101000 101001 101010
경우의 수의 개수가 피보나치 수열이 됨을 확인 할 수 있다.
N = 1 -> 1
N = 2 -> 1
N = 3 -> 2
N = 4 -> 3
N = 5 -> 5
N = 6 -> 8
Tabulation 을 사용하여 간단히 풀어지는 문제였다.
N = int(input())
dp = [0, 1, 1] + [0] * N
for i in range(3, N+1):
dp[i] = dp[i-1] + dp[i-2]
print(dp[N])