백준 C++ 2747번 피보나치 수 ( 배열 )

 

오늘은 점심으로 옛날통닭을 먹었다.

가끔 먹긴 하는데..

맛있다.

아니 근데 자주 사 먹을 거 같지 않다.

ㅋㅋㅋㅋㅋㅋㅋㅋㅋ

 

오늘은! 이름은 자주 들어본 피보나치 수

내 기억으로는 그냥 누적 합으로 알고 있긴 한데..

제대로 알고 있는지 한번 보자!

 

---

 

 

열심히 풀었다.

이론은 그냥

0 + 1 = 1 이거니까..

그다음은 

1 + 1 = 2 이면

ans의 값이 두 번째 값이 되고

두 번째 값이 첫 번째 값으로 가면...

되는 거 아닐까..?

 

근데 틀렸다....

 

나도 이유를 알고 싶었다.

 

오늘은 지 선생이 아니라

제 선생을 찾아갔다.

 

제 선생은 이런 질문을 했다.

int에서 i 가 1부터 인경우가 뭐냐?

 

나는 사실문제 푸는데 전혀 문제가 안된다고 생각했는데

1이라고 한 이유는....

테스트에서 답을 입력했더니 한 사이즈 더 큰 게 나오길래

내가 f2의 값을 이미 1로 지정해 두어서.. 그런 거 아닐까?

라는 생각에 횟수를 한번 빼려고 한 거였다.

 

근데.. 음.. 그러면 n이 1 이면요?라고 하길래 말문이 막혔다.

그렇다....

그러면.... 답을 구할 수가 없네..?

 

조건이 하나 필요하다고 판단했다.

 

 

내가 준 조건은

"첫 번째"

 

처음에 0+ 0이면 쭉 0이니까 f2 두 번째 식에 +1을 해줘서 돌아가게끔 했다.

근데도 틀렸다고 한다.

 

음...

답이 정상적으로 잘 나오는 거 같지만

이것은 n이 1일 때 문제가 된다고 한다.

 

for문은 총 한번 돌게 되며.

ans이 0이 나오게 된다

n이 1일 땐.. ans도 1이 나와야 하는데 말이다.

 

그래서 그냥 크게 조건을 걸게 되었다.

 

네

 

조건을 이렇게 걸었더니 쉽게 풀었습니다.

 

 

나는 항상 풀고, 최고의 답을 물어보는 편이다.

제미나이씨의 대답은

배열로 푸는 방법이 가장 좋다고 했다.

 

사실 이 문제의 식에도 적혀있긴 했다.

fn = f(n-1) + f(n-2)

 

이 식을 활용하면 된다.

문제에서는 n은 45보다 작거나 같다고 했으니

n을 46까지 만들어주고

 

f [0] = 0;

f [1] = 1;

로 해주고

for문으로 2부터 n까지

f [i] = f [i-1] + f [1-2];

해주고

 

출력은

cout >> f [n]; 해주면 끝!

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int F[46];
    
    F[0] = 0;
    F[1] = 1;

    for (int i = 2; i <= n; i++) {
        F[i] = F[i - 1] + F[i - 2];
    }
    cout << F[n];
}

 

이렇게 해주면 뭐 f2는 f1이다 같은 스왑을 안 해줘도 되긴 한다.

그리고 배열 안에 값이 다 들어있기 때문에도 좋다.

그리고 뭐 0과 1 예외처리도 안 해도 된다고 하니

좋은 방법이긴 하다.

---

 

쉬울 줄 알았던 피보나치를 한 시간 넘게 풀며....

뭐 하나 쉬운 게 없다고 생각 한 오늘

하지만 나는 오늘도 지지 않았다.