2193번 이친수

 

문제풀이

이 문제에는 2가지 조건을 만족해야한다.

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

N이 6이라고 가정하자. 그렇다면

N = 1 : 1 (1가지)

N = 2: 10 (1가지)

N = 3: 100 101 (2가지)

N = 4: 1000 1001 1010 (3가지)

N = 5: 10000 10001 10010 10100 10101  (5가지)

N = 6: 100000 100001 100010 100100 100101 101000 101001 101010 (8가지)

값을 얻을 수 있다.

 

여기서 한가지 규칙을 찾을 수 있다.

for문을 돌 경우 i 번째의 값들은 i-1, i-2번째의 값들을 더한 값과 같다.

그렇기 때문에 arr[i] = arr[i-1] + arr[i-2]이란 식을 얻을 수 있다.

 

코드

 

import sys
N = int(sys.stdin.readline())
arr = [0 for _ in range(91)]
for i in range(1,N+1):
    if i == 1: arr[i] = 1
    elif i == 2: arr[i] = 1
    else: arr[i] = arr[i-1] + arr[i-2]
print(arr[N])