[백준 1003] 피보나치 함수

이 문제는 간단한 동적계획법 문제입니다. 이전 값들을 배열에 저장해놓고 다음 배열 값에는 이전 값들을 읽어와 저장을 하는 방식입니다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	static int[][] dp = new int[41][2];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int min = Integer.MIN_VALUE;
		int T = Integer.parseInt(st.nextToken());
		dp[0][0] = 1; dp[0][1] = 0; dp[1][0] = 0; dp[1][1] = 1;
		
		for (int i= 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			if (N > min) {
				min = N;
				for (int j = 2; j <= N; j++) {
					dp[j][0] = dp[j - 1][0] + dp[j - 2][0];
					dp[j][1] = dp[j - 1][1] + dp[j - 2][1];
				}
			}
			
			bw.write(dp[N][0] + " " + dp[N][1] + "\n");
		}
		bw.flush();
	}
}