[PS] 99클럽 코테 스터디 21일차 TIL (피보나치 수)

문제

문제 링크

설명

앞 두 수를 더한 수가 다음 수가 되는 피보나치 수를 구하는 문제

풀이

동적계획법(다이나믹 프로그래밍, DP) : 피보나치 수열은 전형적인 dp 문제다. 초기 상태가 다음 결과에 계속해서 영향을 주는 수열이라 점화식을 도출 할 수 있고, 이를 모든 입력값에 대해 미리 세팅해 두고 꺼내는 방식이다. bottom-up 방식이 익숙해서 해당 방식으로 풀었다. 피보나치 수열에서 제일 처음 나오는 수는 0 이고 그다음 수는 1로 고정이므로, dp 배열에 각각 0, 1 을 넣어주고 시작한다. 그 다음 숫자부터는 앞 두 숫자를 더해서 나오는 결과를 저장하면 된다.

입력되는 수의 범위가 최대 10만 이므로 dp 배열을 미리 10만 크기로 만들어 둔다. 인덱스와 값을 동일하게 사용하기 위해 배열 크기는 n + 1 로 정의한다. dp 문제들은 보통 뒤로 갈수록 수가 매우 커지기 때문에 나눈 나머지를 구하라고 나오기 때문에, dp 배열에 미리 나눈 나머지 값을 저장해 둔다.

반복문을 모두 돌고나면 dp 배열엔 1부터 10만까지 모든 자연수에 대한 피보나치 수가 들어있다. 정답 도출 시에는 단순히 n 번째 값을 꺼내오기만 하면된다.

class Solution {
  public int solution(int n) {
    int answer = 0;
    int MOD = 1234567;

    int[] dp = new int[1000001];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i < dp.length; i++) {
      dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }

    answer = dp[n];
    return answer;
  }
}

회고

사실 피보나치 수열은 너무 잘 알려져 있어 점화식도 금방 도출되고, 점화식을 풀면 답으로 이어지기 때문에 크게 고민할 필요가 없다.

dp 문제의 핵심은 점화식을 찾아내는 것이다. 점화식을 찾는 과정이 문제에 따라 쉽지 않은 경우가 있다. 문제 속에서 어떤 규칙을 발견해 또 다른 작은 문제를 정의해야 한다. 그리고 그 문제를 푸는 것이 결과에 영향을 준다면 방향을 잘 잡았다고 보면된다.