[백준] 1003: 피보나치 함수 - Java (DP)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

 

 

  접근 방식

 

이 문제의 요점은 점화식이 아니라 dp의 특성을 활용하는 것이다.

 

Input

int[] testCase = new int[N]; 으로 입력으로 들어오는 케이스들을 모두 배열에 담았다.

 

 

Solution

int[][] dp = new int[41][2];  0 <= N <= 40 이므로 41로 해주었다. 그리고 내부 배열의 크기는 0과 1의 개수만 저장하면 되니 2로 해준다.

// dp[[0의 개수, 1의 개수]]
int[][] dp = new int[41][2];

 

 

DP 초기설정:  N = 0, N = 1  이었을 때를 설정해 준다.

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

 

 

점화식은 간단하게 알 수 있으니 오픈하겠다.

// 0의 개수
dp[i][0] = dp[i - 2][0] + dp[i - 1][0];
// 1의 개수
dp[i][1] = dp[i - 2][1] + dp[i - 1][1];

 

 

이 문제 정답률이 왜 32% 이지...?

 

 

  풀이

 

 

package src.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class 피보나치함수_1003 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] testCase = new int[N];

        // Input
        for(int i = 0; i < N; i++){
            testCase[i] = Integer.parseInt(br.readLine());
        }


        // Main

        // dp = [[0의 개수, 1의 개수]]
        int[][] dp = new int[41][2];

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


        for(int el : testCase){
            for(int i = 2; i <= el; i++){
                if(dp[i][0] == 0){
                    dp[i][0] = dp[i - 2][0] + dp[i - 1][0];
                    dp[i][1] = dp[i - 2][1] + dp[i - 1][1];
                }

            }

            sb.append(dp[el][0]).append(" ").append(dp[el][1]).append('\n');

        }

        System.out.println(sb);



    }
}