[🥈3 / 백준 2193 / 파이썬] 이친수

 

2193번: 이친수

 

문제

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

1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

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

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

 

예제 입력  3

예제 출력  2

 

풀이

 

이친수는 현재까지 구한 이친수의 끝에 1 혹은 0을 붙여 다음 자릿수의 이친수를 만들 수 있다.

이친수의 특징을 다시 확인해보도록 하자.

 

이친수는 1이 연속해서 나올 수 없다.

즉, 이친수의 끝이 0이라면 0과 1을 붙일 수 있지만, 이친수의 끝이 1이라면 0밖에 붙일 수 없다.

따라서, N자리의 이친수들 끝의 0과 1의 개수를 구한다면 다음 자리수의 이친수의 개수를 구할 수 있는 것이다!

 

예시로, 3자리수의 이친수를 확인해보자.

100 과 101 두 가지가 있다.

이 이친수 두개의 끝에 0과 1을 붙여 4자리수의 이친수를 만들고자 한다.

 

100 + 0, 100 + 1 을 하여 1000, 1001 두 개를 만들 수 있다.

101 + 0 을 하여 1010 하나를 만들 수 있다.

 

1000, 1001, 1010 총 3가지가 나왔다.

 

다시 이 3가지로 5자리 수를 만들어보자.

 

1000 + 0, 1000 + 1, 1010 + 0, 1010 + 1 을 하여 4가지가 나온다.

1001 + 0 을 하여 1가지가 나온다.

 

총 5개의 이친수를 구할 수 있다.

 

즉,

n자리의 0의 수는 n-1의 0의 수 + n-1의 1의 수,

n자리의 1의 수는 n-1의 0의 수가 된다.

 

하지만, 이미 눈치챈 분들도 있겠지만, 위 규칙은 피보나치 수열을 따른다.

따라서 피보나치 수열의 공식인 dp[n] = dp[n-1] + dp[n-2] 를 이용하면 훨씬 쉽게 문제를 풀 수 있다.

 

dp = [1,1]
n = int(input())
while(len(dp) < n):
    dp.append(dp[-1]+dp[-2])
print(dp[-1])