백준 1003번(DP) - 피보나치 함수 (JAVA) 문제 풀이

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

1003번: 피보나치 함수

---

 

✏️ 문제

---

 

🔐 문제 해결

1. 테이블 정의

dp[i][j]의 i값은 i 번째 피보나치 수를 의미하고, j(=0, 1)는 해당 피보나치수의 0의 출력 횟수와 1의 출력 횟수를 나타냅니다.

dp[i][0] = i 번째 피보나치 수의 0 출력 횟수
dp[i][1] = i 번째 피보나치 수의 1 출력 횟수

 

2. 점화식 세우기

3 번째 피보나치 수에 대해서 생각해보겠습니다.

fibonacci(3)은 fibonacci(2) + fibonacci(1) 입니다.

fibonacci(2)는 fibonacci(0) + fibonacci(1) 입니다.

fibonacci(0)은 0을 출력하고 fibonacci(1)은 1을 출력합니다.

그렇다면 fibonacci(3)에 대해서 dp[3][j]를 재정의한다면, 아래와 같습니다.

dp[3][0] = dp[2][0] + dp[1][0];
dp[3][1] = dp[2][1] + dp[1][1];

점화식으로 나타낸다면, 아래와 같이 나타낼 수 있습니다.

// 단, i >= 2
dp[i][0] = dp[i-2][0] + dp[i-1][0];
dp[i][1] = dp[i-2][1] + dp[i-2][1];

 

3. 초기값 설정

fibonacci(0)은 0을 리턴하므로, 다음과 같습니다.

dp[0][0] = 1;
dp[0][1] = 0;

fibonacci(1)은 1을 리턴하므로, 다음과 같습니다.

dp[1][0] = 0;
dp[1][1] = 1;

---

 

🗝 전체 코드

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(bf.readLine());
        int[][] dp = new int[41][2];

        // 초기값 설정
        dp[0][0] = 1; dp[0][1] = 0;
        dp[1][0] = 0; dp[1][1] = 1;

        // fibonacci(3) = fibonacci(2) + fibonacci(1)의 공식을 이용하여 점화식 생성
        for(int i=2; i<=40; i++) {
            dp[i][0] = dp[i-1][0] + dp[i-2][0];
            dp[i][1] = dp[i-1][1] + dp[i-2][1];
        }

        for(int i=0; i<N; i++) {
            int idx = Integer.parseInt(bf.readLine());
            bw.write(dp[idx][0] + " " + dp[idx][1] + "\n");
        }

        bw.flush();
        bw.close();
    }
}