(파이썬 python) 백준 2193번 : 이친수

# 2193번 : 이친수
# 재귀방법으로 피보나치 수열을 만들면 시간복잡도가 크기 때문에 시간초과가 난다.
# tablatoin 방법으로 만들면 시간면에서 훨 효율적이다.

n = int(input())

table = [0]*91

table[1] = 1
table[2] = 1
for i in range(3,n+1):
    table[i] = table[i-1] + table[i-2]

print(table[n])

n=1 : 1

n=2 : 1

n=3 : 2

n=4 : 3

n=5 : 5

n=6 : 8

...

 

처음엔 그냥 숫자들을 적어보다 보니 규칙을 발견할 수 있었다.

피보나치 수열과 같은 규칙이었다.

 

재귀방법으로 문제를 풀게 되면 시간복잡도가 커지고 시간초과가 난다

tablation방법으로 피보나치 수열을 구현하면 시간면에서 더 좋기 때문에 위와 같이 코딩을 해보았다.

 

감사합니다