99클럽 코테 스터디 2일차 TIL + 피보나치 비스무리한 수열

✔️ 오늘의 학습 키워드

• 피보나치 비스무리한 수열

 

✔️ 공부한 내용

• 원래 피보나치 수열의 점화식: f(n) = f(n-1) + f(n-2)이지만
  피보나치 비스무리한 수열의 점화식은 f(n) = f(n-1) + f(n-3)이다. 비슷하지만 다르다.

 

✔️ 오늘의 회고

1.  어떤 문제가 있었고, 나는 어떤 시도를 했는지

  - 피보나치 수열을 이미 풀어본 적이 있었기에 푸는데 크게 어려움이 있진 않았다.

 

 

2.  어떻게 해결했는지

• 동적 계획법(DP)을 활용하여 이전에 계산한 값들을 배열에 저장하고, 점화식에 따라 새로운 값을 계산하는 방식으로 해결했다. 
  초기값 f(1) = f(2) = f(3) = 1을 설정하고, 4번째 항부터는 점화식을 적용하여 계산했다.

#include <iostream>
#include <vector>

using namespace std;

int main() {

    int n;
    cin >> n;
    
    // 기본 케이스 처리
    if (n <= 3) {
        cout << 1 << endl;
        return 0;
    }
    
    // 수열을 저장할 배열 선언
    // 문제에서 n이 최대 116까지 가능하므로, 충분한 크기로 설정
    vector<long long> fib(n+1, 0);
    
    // 초기값 설정
    fib[1] = 1;
    fib[2] = 1;
    fib[3] = 1;
    
    // 점화식 f(n) = f(n-1) + f(n-3)을 이용해 수열 계산
    for (int i = 4; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-3];
    }
    
    cout << fib[n] << endl;
    
    return 0;
}

 

3.  무엇을 새롭게 알았는지

• 피보나치 수열만이 아닌 비스무리한 수열도 있다는 것을 알았다.