[BOJ] [Python] 2193번 : 이친수

문제의 조건을 살펴보자.

 

1. 0으로 시작하지 않는다.

2. 1이 두 번 연속으로 나타나지 않는다.

 

 

이를 간단하게 나타내보자.

 

규칙

 

1. 1로 시작한다.

2. 1뒤에는 0이 온다.

3. 0뒤에는 1또는 0이 온다.

 

 

코드를 작성하기 전, 예시를 몇 개 작성해보자

 

5개의 예시

 

위 예시를 표로 나타내면 아래와 같다. 

 

 

처음에 찾은 규칙이랑 같이 고려해보면 점화식을 찾을 수 있다.

 

n의 0의 개수 : 0개 ( n = 1 )

n의 1의 개수 : 1개 ( n = 1 )

 

n의 0의 개수 : n -1의 0의 개수 + n - 1의 1의 개수 ( n > 1 )

n의 1개 개수 : n - 1의 0의 개수  ( n > 1 )

 

 

num = int(input())

zero = 0
one = 1

for _ in range(num - 1):
    tmp = zero

    zero += one

    one = tmp

print(zero + one)