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

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

1003번: 피보나치 함수

 

<문제 분석>

1. DP 테이블의 성격 정의
  - DP[N][2]로 생성해서 DP[i][0]에는 0의 출력 횟수, DP[i][1]에는 1의 출력 횟수를 저장한다.

  - N <= 40
2. 초기값 설정
  - DP[0]과 DP[1]의 값을 초기값으로 정해서 미리 입력한다.
3. 점화식
  - DP[N] = DP[N-1] + DP[N-2]

 

메인 함수에서 미리 0 to 40까지 DP 테이블의 값을 채워놓고 테스트케이스를 돌릴 때는 이미 생성한 DP 테이블의 값을 바로 출력하는 식으로 구현했다.

 

<코드 구현>

import java.util.Scanner;
import java.lang.Math;

public class Main {
	static int T;//입력 데이터의 개수
    static int Data[];
    static int DP[][] = new int[40+1][2];

	public void InputData()
	{
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
        Data = new int[T];
		for (int i = 0; i < T; i++) 
		{
			Data[i] = sc.nextInt();
		}
		sc.close();
	}
	
	public void Solve() {
        // 1.DP 테이블 초기화 및 값 종류 정하기
        // 피보나치 수열의 0과 1 횟수 저장
        for (int i=0; i<=40; i++) {
            for (int j=0; j<2; j++) {
                DP[i][j] = -1;
            }
        }
        // 2. 초기값 설정
        DP[0][0] = 1;
        DP[0][1] = 0;
        DP[1][0] = 0;
        DP[1][1] = 1;

        // 3. N만큼 반복해서 DP 테이블을 채운다
        for (int i=2; i<=40; i++) {
            for (int j=0; j<2; j++) {
                DP[i][j] = DP[i-1][j] + DP[i-2][j];
            }
        }
	}
    
	public static void main(String[] args) 
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();

		//출력
		for (int i = 0; i < T; i++) 
		{
            System.out.println(DP[Data[i]][0]+" "+DP[Data[i]][1]);
		}
	}
}

 

<제출 결과>

 

<후기>

코드 구현까지 29분 30초 소요됨.