재귀를 통한 풀이 (시간초과..)
재귀를 이용하여 풀어보려고 했건만, 시간초과로 실패했다. 시간제한 2초인데도 걸리다니 빡세구만…
# 입력
import sys
n = int(sys.stdin.readline())
count = 0
# 처리
def pinary(arr = [1]):
if len(arr) == n:
global count
count += 1
return
else:
if arr[-1] == 1:
pinary(arr + [0])
else:
pinary(arr + [0])
pinary(arr + [1])
pinary()
print(count)
dp을 이용한 풀이
러닝타임을 줄이기 위해서 주어진 이친수의 규칙을 파악해보았다. (0으로 끝나는 길이가 n인 이친수의 갯수)를 $ a_{n} $ (1로 끝나는 길이가 n인 이친수의 갯수)를 $ b_{n} $ 이라고 두면 $ a_{n} = a_{n-1} + b_{n-1} $ $ b_{n} = a_{n-1} $ 의 식을 만족한다. $ a_{0} = 0, b_{0} = 1 $ 의 초항을 대입하여 점화식을 풀면 n길이의 이친수의 갯수를 쉽게 구할 수 있다.
# 입력
import sys
n = int(sys.stdin.readline())
a,b=0,1
# 처리
for _ in range(n-1):
a,b=a+b,a
print(a+b)