#1003 : 피보나치 함수

풀이방법

사용된 것:

다이나믹 프로그래밍(DP)

 

2022.03.28

매우 간단한 문제이다.

정수 k를 입력받았을 때 출력해야 하는 문자열을 "$zero_k$ $one_k$"라고 할 때,

 

$zero_k = zero_{k-2} + zero_{k-1}$

$one_k = one_{k-2} + one_{k-1}$

이다.

 

따라서,

크기가 41인 배열을 만든 후

배열의 0번 요소부터 40번 요소까지 반복문을 돌리며 덧셈을 해주면

문제에서 요구할 수 있는 모든 정수에 대한 답이 저장된 배열이 완성된다.

 

이후 들어오는 입력값에 따라 이 배열에서 정답을 꺼내 출력하면 된다.

 

코드

Java(2022.03.28)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static StringBuilder sb;
	
	static void print(Unit u) {
		sb.append(u.zero + " " + u.one + System.lineSeparator());
	}

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();
		
		Unit[] dp = new Unit[41];
		
		dp[0] = new Unit(1, 0);
		dp[1] = new Unit(0, 1);
		
		for(int i = 2; i<41; i++) {
			int zero = dp[i-2].zero + dp[i-1].zero;
			int one = dp[i-2].one + dp[i-1].one;
			dp[i] = new Unit(zero, one);
		}
		
		//정답 출력
		int t = Integer.parseInt(br.readLine());
		for(int i = 0; i<t; i++) {
			print(dp[Integer.parseInt(br.readLine())]);
		}
		System.out.print(sb);
	}

}

class Unit{
	int zero;
	int one;
	
	public Unit(int zero, int one) {
		this.zero = zero;
		this.one = one;
	}
}