[백준] 1003번: 피보나치 함수 - python

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

DP로 접근하는 코드

 

사실 이 코드는 비효율적이다.. DP로 작성하긴 했으나, 항상 처음부터 다시 구현하는 단점이 있다.

이를 해결하기 위해선 값의 인덱스를 저장하거나, 가장 큰 입력을 먼저 받은뒤 값을 꺼내기만 하면 된다.

그러나 통과가 되길래.. 일단 패스.. 집가고 싶어서..

 

n = int(input())

for i in range(n):
    dp = [[1,0], [0,1], [1,1], [1,2]]
    m = int(input())
    if m < len(dp):
        print(*dp[m])
        continue
    for i in range(4, m+1):
        x, y = dp[i-1][0]+dp[i-2][0],dp[i-1][1]+dp[i-2][1]
        dp.append([x, y])

    print(*dp[m])

 

이렇게 저장하는게 맞는지 다른사람코드를 확인했는데.. 와우

아예 배열에 저장을 하지 않고 a, b 두 변수만으로도 푼 코드가 있었다.

 

T = int(input())
for _ in range(T):
    N = int(input())
    a, b = 1, 0 # 0과 1이 호출된 횟수
    for i in range(N):
        # 0은 1이 호출된 횟수만큼, 1은 0과 1이 호출된 합만큼 출력됨
        a,b = b, a+b 
    print(a,b)
출처: https://edder773.tistory.com/64 [개발하는 차리의 공부 일기:티스토리]

 

한 수 배우고 갑니다..