백준 2193번 문제 바로가기

재귀를 통한 풀이 (시간초과..)

재귀를 이용하여 풀어보려고 했건만, 시간초과로 실패했다. 시간제한 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)