[백준/BOJ] 1003 피보나치 함수

[백준/BOJ]

문제 # https://www.acmicpc.net/problem/1003

 

주어진 정수를 인수로 피보나치 함수를 호출하게 될 때, 0과 1을 인수로 피보나치 함수를 호출하는 경우가 각각 몇 번인지 구하는 문제

주어지는 정수는 40까지 주어지지만, 실제로 모든 피보나치함수를 호출할 수 없으니 dp를 이용하여 해결해야하는 문제

 

 

내가 작성한 코드

package boj;

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

public class BOJ1003 {
	static final int MN = 40;
	static int[][] dp;
	static int T;
	static int N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		init();
		
		T = Integer.parseInt(br.readLine());
		for(int i=0; i<T; ++i) {
			N = Integer.parseInt(br.readLine());
			System.out.println(dp[N][0]+" "+dp[N][1]);
		}
		
	}
	private static void init() {
		dp = new int[MN+1][MN+1];
		dp[0][0] = 1;
		dp[0][1] = 0;
		dp[1][0] = 0;
		dp[1][1] = 1;
		
		for(int i=2; i<=MN; ++i) {
			dp[i][0] = dp[i-2][0] + dp[i-1][0];
			dp[i][1] = dp[i-2][1] + dp[i-1][1];
		}
	}

}

 

풀이 및 배운 점

2차원 배열 dp[i][j] 를 정의했다. `j`는 `0`과 `1`이 될 수 있고, `i`는 `0`부터 `40`까지 올 수 있다.

dp[i][0]과 dp[i][1]은 각각 `i`번째 수에서 `0`과 `1`이 출력되는 횟수로 정하여 주어진 수를 입력받기 전, 40까지 모든 경우의 수를 모두 계산하고, 입력 받은 즉시 각각 경우를 출력하는 방식으로 풀었다.

 

풀고나서 다른 사람들의 풀이방식을 참고해보니, 2차원 배열로 풀거나 zero[], one[] 과 같이 각각 1차원 배열을 이용하여 푸는 방식을 주로 선택하여 푼 것 같았다.

 

그리고 다른 분들의 코드를 보면서 느낀 것이 아무리 짧은 코드더라도 StringBuilder를 이용하는 습관을 들이도록 해야겠다.