[Algorithm] 99클럽 코테 스터디 21일차 TIL | 백준_피보나치 함수(1003번)

📝문제

 

💡풀이

동적 계획법의 기본이 피보나치 수열인데 피보나치 수열의 함수가 주어지고 출력되는 1과 0의 개수를 구하라니, 이 또한 규칙이 있겠다고 생각했다.

N	0출력	1출력
1	0	1
2	0	1
3	1	2
4	2	3

N별로 출력값을 구해보니 

dp[N][0] = > N이 호출 됐을 때 0 출력 개수

dp[N][1] => N이 호출 됐을 때 1 출력 개수 라고 하면

dp[N][0] = dp[N-2][0] + dp[N-1][0]

dp[N][1] = dp[N-2][1] + dp[N-1][1] 의 규칙을 가지는 것을 확인했다.

 

전체 풀이

import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        int[][] dp = new int[41][2];
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[1][0] = 0;
        dp[1][1] = 1;
        for(int i = 2; i < 41; i++){
            dp[i][0] = dp[i-2][0] + dp[i-1][0];
            dp[i][1] = dp[i-2][1] + dp[i-1][1];
        }

        for(int i = 0; i < T; i++){
            int n = Integer.parseInt(br.readLine());
            sb.append(dp[n][0]).append(" ").append(dp[n][1]).append("\n");
        }

        System.out.println(sb);
    }
}

 

🤔Review

복잡한 건 규칙 찾기도 힘들고 간단한건 바로 규칙이 보이는 유형이 dp같다. 갠적으로 어려워하는 유형인데 이번주 동적계획법 연습 제대로 해보자!