[백준] 1003번 피보나치 함수 JAVA (자바) 풀이

문제 1003번 (DP)

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

 

• fibonacci(3) = fibonacci(2)와 fibonacci(1) 
• fibonacci(2) = fibonacci(1)과 fibonacci(0)

 

 

 

 

[입력]

 :  첫째 줄에 테스트 케이스의 개수 T

    각 테스트 케이스에 N이 주어진다 ( N은 40보다 작거나 같은 자연수 또는 0)

 

 

[출력]

 :  각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력

[설명]

 

DP 알고리즘

: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법

  DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다

 

탑다운 (Top-Down)	보텀업 (Bottom-Up)
작은 크기로 문제를 나눠서 해결	작은 것부터 해결해서 점차 빌드업
메모제이션 (memoization)	타뷸레이션 (tabulation)
일부만 계산해도 답이 나올 때	모두 계산해야 답이 나올 때
재귀	반복문
시간 복잡도 O(n)	시간 복잡도 O(n)

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = 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;
            
        while(T-->0){
            int N = Integer.parseInt(br.readLine());
            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]);
        }
    }
}

 

 

 [해설]
     

 :  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int T = Integer.parseInt(br.readLine());
    int dp[][] = new int[41][2];
        
 :  dp[0][0] = 1;  0을 선택했을 때 0의 개수
    dp[0][1] = 0;  0을 선택했을 때 1의 개수
    dp[1][0] = 0;  1을 선택했을 때 0의 개수
    dp[1][1] = 1;  1을 선택했을 때 1의 개수
            
 :  while(T-->0){  테스트 케이스만큼 반복
            int N = Integer.parseInt(br.readLine());  N입력
            for(int i=2; i<=N; i++){  2부터 시작하기
                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]);  0개수 1개수 출력
    }
    

    

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

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

 

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *