# [til] 알고리즘 백준 14495

### 🧑‍💻 오늘의 문제: 피보나치 비스무리한 수열

* **출처**: 백준 온라인 저지 (BOJ)
    
* **문제 요약**:  
    피보나치 비스무리한 수열을 다음과 같이 정의한다.
    
    > f(n) = f(n-1) + f(n-3)  
    > 단, 초기값은 f(1) = f(2) = f(3) = 1 이다.
    
    자연수 n이 주어졌을 때, 이 수열의 n번째 수를 구하는 문제이다.
    

### 📌 풀이 과정

* 수열을 저장할 배열을 선언하고 초기값을 미리 채워준다.
    
* 반복문을 사용하여 4번째 수부터 n번째 수까지 계산하여 배열에 저장한다.
    
* 마지막으로 배열의 n번째 값을 출력한다.
    

### 🖥️ 내가 작성한 코드

```python
import sys

n = int(sys.stdin.readline())

fibonacci_arr = [1, 1, 1]
if n > 3:
    for i in range(3, n):
        fibonacci_num = fibonacci_arr[i-1] + fibonacci_arr[i-3]
        fibonacci_arr.append(fibonacci_num)

print(fibonacci_arr[n-1])
```

### 💡 문제 해결 방법과 복기

* 기본적인 DP(동적 프로그래밍) 유형의 문제였다.
    
* 점화식 그대로 코드를 작성했고, 특별히 어려운 부분은 없었다.
    
* 메모리를 조금 더 절약하고 싶다면 배열 대신 변수 몇 개만 써서 공간을 최적화할 수도 있을 것 같다.
    

---

### 🔍 추가적으로 찾아본 더 좋은 풀이 방법

다른 사람들의 풀이를 참고해보니, 더 효율적인 메모리 관리를 위해 배열을 쓰지 않고 변수 몇 개로만 관리하는 방법이 있었다.  
왜냐하면 피보나치 수열과 비슷하게 특정 인덱스만 기억하면 되는 문제라서 배열 전체를 저장하지 않아도 되기 때문이다.

**최적화된 코드 예시**

```python
import sys

n = int(sys.stdin.readline())

a, b, c = 1, 1, 1
for _ in range(4, n + 1):
    a, b, c = b, c, a + c

print(c)
```

**이 코드의 장점:**

* 배열을 사용하지 않아 공간복잡도 측면에서 효율적이다.
    
* 간단한 변수만을 사용하므로 메모리 사용량이 적다.
    

---

### ✨ 느낀점 & 앞으로의 계획

* 단순히 문제를 해결하는 것에서 그치지 않고, 다른 사람들의 풀이를 찾아보며 효율적이고 간결한 코드를 배우는 습관이 중요하다고 느꼈다.
    
* 앞으로 하루 하나씩 꾸준히 알고리즘 문제를 풀면서, 문제 풀이 실력뿐 아니라 다양한 최적화 테크닉도 함께 익혀야겠다.