BOJ/백준 1003 피보나치 함수

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

 

해결 아이디어

1학년 시절 아무것도 모르고 깡으로 풀었다가 틀린 전적이 있어서 다른 알고리즘을 사용해야 시간내에 해결 할 수 있다는 것을 알게되어서

DP를 사용하면 해결 할 수 있을것으로 판단했다.

문제가 0과 1의 개수를 구하는 것이고 피보나치수는 이전 값을 가지고 다음 값을 계산 하는 것이기 때문에 n이 0일때와 n이 1일때 수를 알고 있으면 이 값을 바탕으로 나머지 값도 모두 구할 수 있다.

 

dp[x][y]에서 x는 n값 y = 0은 0의 개수 y = 1은 1의 개수이다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        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 - 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 num = Integer.parseInt(br.readLine());
            bw.write(dp[num][0] + " " + dp[num][1] + "\n");
        }
        bw.flush();
    }    
}