[백준/c++] 14495번 : 피보나치 비스무리

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

문제

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!

입력

자연수 n(1 ≤ n ≤ 116)이 주어진다.

출력

n번째 피보나치 비스무리한 수를 출력한다.

---

구상

우선 배열을 만들어줘야겠지? 벡터로 만들어보자. 편의를 위해 0번째 인덱스는 비우고, 1번째 인덱스부터 차례대로 넣어줘야겠다. 1,2,3번째 인덱스는 1로 세팅해두고 for문을 통해 그다음 수열을 차례로 채워주면 되겠다 !

코드

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v(n+1);
    v[1] = v[2] = v[3] = 1;
    
    for (int i=4; i<=n; i++) v[i] = v[i-1] + v[i-3];
    cout << v[n];

    return 0;
}​

 이렇게 코드를 짜니 예제들은 잘 나왔다. 하지만, 제출하니 틀렸다고 떠서 계속 고민해보았다. 질문게시판도 보고 하니, 숫자가 커지면 4바이트 이상의 숫자들이 입력돼서 int로 감당이 안돼서 틀렸던 것 같다. 그래서 int를 long으로 고쳐주었다.

 하지만, 이번엔 런타임 에러가 발생하였다. 어떤 부분이 문제가 있을까 고민해보았다. n이 1일땐 어떤 일이 발생하지?라고 생각하니 바로 답이 나왔다. n이 1이면 벡터의 크기는 2인데, 코드는 지금 v[2]=1, v[3]=1을 무턱대고 넣어주고있으니 문제가 발생하는 것이다! 그래서 v[1], v[2], v[3]을 무턱대고 넣지않고, 조건을 걸어주니 해결되었다. 아래는 수정 완료된 코드이다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<long> v(n+1);
    
    if (n >= 1) v[1] = 1;
    if (n >= 2) v[2] = 1;
    if (n >= 3) v[3] = 1;
    
    for (int i=4; i<=n; i++) v[i] = v[i-1] + v[i-3];
    cout << v[n];

    return 0;
}