백준 1003번: 피보나치 함수 [DP] - Java

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

쉽구만 하고 재귀로 풀었는뎅 역시 시간초과가 났다.

	public static int fibo(int num) {

		if(num==0) {
			zero++;
			return 0;
		} else if(num==1) {
			one++;
			return 1;
		} else {
			return fibo(num-1)+fibo(num-2);
		}

	}

 

DP 메모제이션을 이용하여 풀었다.

2차원배열을 통해 숫자별로 0의갯수와 1의갯수를 저장한다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static int n;
	public static int[][] dp;

	public static void main(String[] args)  {

		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();

		for (int t = 0; t < T; t++) {
			n = sc.nextInt();

			dp = new int[n + 2][2]; // 숫자별 0의갯수, 1의갯수 저장 용도

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

			for (int i = 2; i <= n; i++) {
				for (int j = 0; j < 2; j++) {
					dp[i][j] = dp[i - 1][j] + dp[i - 2][j];
				}
			}

			System.out.println(dp[n][0] + " " + dp[n][1]);

		}

	}

}

 

DP의 길은 험하지만 오늘도 책상앞에 앉은 나를 칭찬해~~