99클럽 코테 스터디 2일차 TIL - 피보나치 비스무리한 수열 (백준 14495번)

오늘의 학습 키워드

- 피보나치 수열

- DP(동적 계획법)

- 점화식

- 배열

- 자료형 범위

- long, int 오버플로우

---

공부한 내용 정리

오늘은 백준 14495번 문제인 피보나치 비스무리한 수열을 풀었다.

 

점화식이 일반적인 피보나치 수열과는 달라서 f(n) = f(n-1) + f(n-3)로 정의되어 있고, 초깃값은 f(1) = f(2) = f(3) = 1로 주어진다.

 

DP 배열을 활용해 반복문으로 수열을 구현했고, 배열의 인덱스는 문제 조건에 맞춰 1부터 사용했다.

---

소스코드

import java.io.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());

    long[] fibo = new long[117];
    fibo[1] = fibo[2] = fibo[3] = 1;

    for (int i = 4; i <= n; i++) {
      fibo[i] = fibo[i - 1] + fibo[i - 3];
    }

    System.out.println(fibo[n]);
  }
}

---

오늘의 회고

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

처음에는 int[] 배열을 사용해 수열을 구현했는데, n=116까지 계산하는 경우 int 범위를 초과해서 오답이 발생했다.

 

• 어떻게 해결했는지

출력 값이 int 범위를 넘는다는 사실을 확인하고, 배열 자료형을 long[]으로 수정해 해결했다.

또한 백준에서 안정적인 입력 처리를 위해 Scanner 대신 BufferedReader를 사용하는 방식으로 변경했다.

 

• 무엇을 새롭게 알았는지

• DP 문제에서 결과 값이 클 수 있으므로 자료형 범위 확인은 반드시 필요하다는 것을 다시 한 번 느꼈다.

• 점화식을 정확히 구현하는 것도 중요하지만, 초기값 설정 역시 정확히 해야 전체 수열이 올바르게 계산된다.

 

• 내일 학습할 것은 무엇인지

내일은 DP 문제 중에서 2차원 배열을 사용하는 유형을 풀어보며, 다양한 점화식 구현을 연습할 예정이다.

---