백준 2193 이친수 파이썬 풀이

백준 2193

풀이

규칙을 찾는 것이 우선이다.

 

0으로 시작하지 않고, 1이 연속으로 나오지 않는 이진수의 수를 찾으면 된다.

 

1자리 수일 때 1 하나, 2자리 수일 때 10 하나, 3자리 수일 때 100, 101로 2개이다. 아직까진 무슨 규칙인지 모른다.

 

4자리 수일 때 1000, 1001, 1010 3개이다. 5자리 수는 1000, 10101, 10010, 10001, 10100 이렇게 5가지가 나온다.

 

이를 통해 2자리수 이상일 때, 10으로 시작한다는 공통점이 있고, 그 전 자리수에서 0과 1을 채워넣는다는 사실과 그 전전자리수와 합하면 1이 겹치지 않게 만들  수 있다는 규칙을 찾을 수 있다. 

 

1. a에 자리수를 입력받는다.

a = int(input())

 

2. 문제에 90까지라 했으므로 인덱스가 90을 가르킬 수 있도록 리스트를 만든다.

b = [0 for i in range(91)]

 

3. 미리 구한 값들 몇 개를 집어넣는다. 

b[1]=1

b[2]=1

b[3]=2

for i in range(3,91):

  b[i]=b[i-2] + b[i-1]

 

a일 때의 개수를 뽑는다.

print(b[a])