2748번: 피보나치 수2(백준 C++)

2748번: 피보나치 수2 링크

코드

#include <iostream>
using namespace std;

int main() {
    long long f1 = 0, f2 = 1, f3;
    int n;
    cin >> n;

    if(n == 0) cout << f1;
    if(n == 1) cout << f2;
    else{
        for(int i=2; i<=n; i++){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        cout << f3;
    }
}

풀이 및 사견

단골 사골문제, 피보나치가 죽지않고 또 돌아왔다.
어제로 이제 백트래킹 단계가 끝나고 DP로 들어왔다... 5~6개월 전에 문제 풀었을때 DP단계 거의 다 풀고 때려쳤었는데
그래고 한 달정도 꾸준히 문제풀다보니 따라잡았다. 조금 있으면 아예 새로운 단계를 풀겠지 기대된다.

어쨌든 사골문제, 한 번 풀어보자.

주의사항

• N은 90이하의 자연수이다.

피보나치를 90까지 돌리게 되면 수가 무지막지하게 커져서 int형으로는 감당이 안된다.
그렇기 때문에 나는 long long 타입을 사용했다.

이것만 주의하면 늘 하던대로 조리하면 된다.

다만 재귀로 하느냐 반복으로 하느냐의 차이인데, 이번에는 DP.
풀이단계를 소분화해서 돌리는 방식이기 때문에 반복문을 사용하겠다.

Fn = Fn-1 + Fn-2

이 점화식을 그대로 사용 하면 된다.

점화식에 변수가 3개 들어가니, 우리도 변수를 3개 만들어준다.

long long f1 = 0, f2 = 1, f3;

그리고 그 점화식대로 반복문을 만들어 주면

for(int i=2; i<=n; i++){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }

이렇게 된다.

구하려고 하는 단계 이전의 두 수를 계속해서 업데이트해주면서 반복해서 더해나가는 방식이다.