링크

1003 피보나치 함수

문제

풀이

이 문제를 하나하나 적다보니 규칙을 찾았다.
dp[n][k] -> n은 숫자, k는 n의 0과 1의 갯수이다.
즉 dp[3][0] = f(3)일때 0의 갯수 1, dp[3][1] = f(3)일때 1의 갯수, 2이다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

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

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


        for(int t=0;t<testCase;t++){
            int n = Integer.parseInt(br.readLine());

            //첫번째는 n, 두번째는 0, 1의 갯수
            int[][] dp = new int[n+1][2];

            //0일때 셋팅
            if(n >= 0){
                dp[0][0] = 1;
                dp[0][1] = 0;
            }

            //1일때 셋팅
            if(n >= 1){
                dp[1][0] = 0;
                dp[1][1] = 1;
            }

            for(int i=2;i<=n;i++){
                dp[i][0] = dp[i-1][0] + dp[i-2][0];
                dp[i][1] = dp[i-1][1] + dp[i-2][1];
            }

            System.out.println(dp[n][0] + " " + dp[n][1]);

        }

    }


}