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

문제 링크 : https://www.acmicpc.net/problem/1003

이 문제는 dp 문제입니다. 문제가 요구하는 점화식을 만들어낼 수 있다면 쉽게 풀 수 있습니다.

문제에서는 0이 출력된 횟수와 1이 출력된 횟수를 물어보고 있습니다. 만약 입력된 수가 0이라면 0은 1번, 1은 0번 출력될 것입니다. 마찬가지로 입력된 수가 1이라면 0은 0번, 1은 1번 출력됩니다.

그렇다면 입력된 수가 2라면 어떻게 될까요? 2라면 1이었을때의 출력 횟수와 0이었을 떄의 출력 횟수를 더한 값이 됩니다. 즉 문제에서 요구하는 n의 수를 입력받았을 때 0과 1의 횟수에 대한 점화식은 각각

zeroNum[n] = zeroNum[n-1] + zeroNum[n-2]

oneNum[n] = oneNum[n-1] + oneNum[n-2]

가 됩니다. 위의 점화식을 토대로 문제를 푸시면 되겠습니다.

다음은 코드입니다.

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        while(T-->0){
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int[] zeroNum = new int[41];
            int[] oneNum = new int[41];

            zeroNum[0] = 1;
            zeroNum[1] = 0;

            oneNum[0] = 0;
            oneNum[1] = 1;

            for(int i=2;i<=N;i++){
                zeroNum[i] = zeroNum[i-1] + zeroNum[i-2];
                oneNum[i] = oneNum[i-1] + oneNum[i-2];
            }

            sb.append(zeroNum[N]);
            sb.append(" ");
            sb.append(oneNum[N]);
            sb.append("\n");
        }

        System.out.println(sb);
    }
}