🥈 24417번: 알고리즘 수업 - 피보나치 수 2

👉🏻 24417번: 알고리즘 수업 - 피보나치 수 2

mod = int(1e9) + 7
n = int(input())
ans = n-2
prev, cur = 1, 1

for _ in range(ans):
    nv = (prev + cur) % mod
    prev, cur = cur, nv

print(cur, ans)

왜 이렇게 풀었을까?

• 해당 문제는 제목만 봐도 파악할 수 있듯, 피보나치 수에 관한 내용을 다루고 있습니다. 피보나치 수를 알고리즘으로 구하기 위해서는 대표적으로 재귀, DP의 2가지 방법을 사용할 수 있는데, 문제에서는 두 개를 모두 요구하고 있습니다.

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

• 출력값 중 위 코드에서 코드1이 실행되는 횟수가 포함되어 있습니다. 이 횟수는 결과적으로 따져보면, 해당 fib(n)의 결과값이나 다름없기 때문에 fib(n) 자체를 구한 뒤 출력해주면 됩니다.
• 출력값의 두 번째는 코드2를 통한 DP의 실행 횟수를 묻고 있습니다. 말 그대로 DP의 실행 횟수를 구해 출력하면 되는데, 저는 일반적인 배열 방식의 DP로 접근하였더니 메모리 초과가 발생하였습니다.
• 생각해보니 여러 번 특정 DP 배열의 값을 호출하거나 중간 값을 활용하지 않는다면, 변수 두 개만으로 최대공약수를 구하는 방식처럼 접근해도 충분히 풀 수 있었습니다. 그래서 저는 prev와 cur 변수의 초깃값을 설정한 뒤, 이를 통해 쭉 피보나치 수를 계산해나갔습니다.
• 최종적으로 문제에서 값이 너무 커지는 것을 방지하여 1,000,000,007로 나눈 나머지를 출력하라고 명시하였기에 int(1e9) + 7를 사용해 그대로 수행하여 풀이하였습니다.