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

코드

일반dp 느낌의 풀이

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

public class Main {
	static int zero; // 이번 순서
	static int one; // 다음순서
	static int zero_plus_one;
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			fibonacci(N);			
			sb.append(zero).append(' ').append(one).append('\n');
		}
		System.out.println(sb);
 
	}
 
	public static void fibonacci(int N) {
		// 반드시 초기화 해야한다.
		zero = 1;
		one = 0;
		zero_plus_one = 1;
 
		for (int i = 0; i < N; i++) {
			zero = one;
			one = zero_plus_one;
			zero_plus_one = zero + one;
		}
 
	}
 
}

해당 코드에 대한 로직의 전체적인 설명

1. 2차원 정수 배열 dp를 선언하고, 크기는 41x2이며, dp[i][0]에는 i 번째 피보나치 수열에서 0이 호출된 횟수,dp[i][1]에는 1이 호출된 횟수를 저장.

2. 사용자 입력을 받아 테스트 케이스 수 T를 설정

3. dp 배열의 초기값을 설정
   이때, 피보나치 수열의 첫 번째와 두 번째 숫자는 각각 0과 1이므로, 호출 횟수도 각각 1회와 1회로 설정합니다.

   dp[0][0]= 1;
   dp[0][1]= 0;
   dp[1][0]= 0;
   dp[1][1]= 1;

4. 각 테스트 케이스에 대해 사용자로부터 입력받은 정수 N에 대하여 피보나치 함수를 호출하고, 결과를 출력할 문자열에 피보나치 함수에서 구한 0과 1의 호출 횟수를 추가합니다. --> while 안에서

5. fibonacci 메서드를 정의해야합니다.
   이 함수는 피보나치 수열에서 n 번째 수에 대한 0과 1의 호출 횟수를 계산합니다.

   이 메서드의 동작
   dp 배열에 저장된 이전 결과를 사용해서 이미 계산된 값이 있는지 확인합니다.

   • 만약 값이 null이 아니라면, 이미 계산된 값을 반환합니다.
   • 값이 null인 경우, 피보나치 점화식에 따라서 재귀적으로 함수를 호출해서 값을 계산하고, 배열에 저장해 나갑니다.
   • 계산된 dp[n] 배열을 반환합니다.

모든 테스트 케이스에 대한 결과가 문자열에 저장되면, 최종 결과물을 출력합니다.
이 코드는 피보나치 수열에서 0과 1의 호출 횟수를 구하는 문제를 동적 프로그래밍(dp)방식으로 해결하였습니다.

dp로 풀이

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

class Main{
    static Integer [][] dp = new Integer [41][2];
    public static void main(String[]args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        // 호출 횟수 
        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());
            fibonacci(N);
            sb.append(dp[N][0]+" "+dp[N][1]).append("\n");
        }System.out.print(sb+"\n");
    }
    static Integer[] fibonacci(int n){
        if(dp[n][0]==null || dp[n][1] ==null){
            dp[n][0] = fibonacci(n-1)[0]+fibonacci(n-2)[0];
            dp[n][1] = fibonacci(n-1)[1]+fibonacci(n-2)[1];
        }
        return dp[n];
    }
}

코드 설명

위 코드와 비슷하나, 중요한 키 포인트는
피보나치 수열에서 0과 1의 호출 횟수를 반복문을 사용하여 순차적으로 계산합니다. 이렇게 하면 재귀 호출을 사용하지 않아 시간 및 메모리 효율이 향상되며 시간복잡도적으로 좋게 됩니다.