문제 이해

피보나치 수를 구할 때, fibonacci(0) = 0, fibonacci(1) = 1이 출력되며, 나머지 경우에는 피보나치 점화식인 fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)가 수행된다.

fibonacci(n)을 구하고 싶을 때, 0과 1이 몇 번 출력되는지 구하는 문제이다.

---

문제 풀이

$DP\left[i\right]\ =\ DP\left[i-1\right]\ +\ DP\left[i-2\right]$
피보나치 함수의 점화식이다.

만약 fibonacci(i-1)에 0이 a번, 1이 b번 나왔다고 생각하자.
또한 fibonacci(i-2)에 0이 A번, 1이 B번 나왔다고 생각하자.
이 경우, fibonacci(i)는 0이 (A+a)번, fibonacci(i)는 1이 (B+b)번 출력될 것이다.

따라서, 2차원 배열을 준비하여 중간 과정을 저장하는 방식으로 문제를 풀었다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static long[][] ans;
    // ans[i][0] : fibonacci(i)에서 0이 출력 되는 횟수
    // ans[i][1] : fibonacci(i)에서 1이 출력 되는 횟수

	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		int T  =sc.nextInt();
		
		ans = new long[41][2];
		ans[0][0] = 1;
		ans[0][1] = 0;
		ans[1][0] = 0;
		ans[1][1] = 1;
		
		for(int i =2;i<41;i++) {
			ans[i][0] = ans[i-1][0] + ans[i-2][0];
			ans[i][1] = ans[i-1][1] + ans[i-2][1];
		}
		
		for(int t=0;t<T;t++) {
			N = sc.nextInt();
			sb.append(ans[N][0]).append(" ").append(ans[N][1])
                                            .append("\n");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 3번째 줄 틀렸습니다 : 답이 될 수 있는 최댓값이 int 범위를 넘어가 long으로 처리했어야 했다.

• 2번째 줄 틀렸습니다 : 출력 형식을 잘못 설정하여 틀렸다.