BOJ 1003 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

 

문제 분석

- dp문제이다. 

- 0이 나오는 경우는 해당 숫자의 -1번째와 -2번째의 숫자를 더한 숫자이고, 1이 나오는 경우도 마찬이다.

- 각 값들을 배열에 저장해놓고 최종 값만 출력한다.

 

 

문제 풀이

1) 2차원 배열을 선언하여 0번 열에는 0이 출력되는 횟수를 넣는다. 1번 열에는 1이 출력되는 횟수를 넣는다.

2) 각 횟수는 -1과 -2한 각각의 값을 더한 값과 동일하다.

3) 해당 숫자의 [0]번 열과 [1]번 열을 출력하면 각각 0이 출력된 횟수와 1이 출력된 횟수를 의미한다.

 

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

public class Main {

	private static long[][] map;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			int N = Integer.parseInt(br.readLine());
			map = new long[41][2];

			map[0][0] = 1;
			map[0][1] = 0;
			map[1][0] = 0;
			map[1][1] = 1;
			
			for (int j= 2; j <= N; j++) {
					map[j][0] = map[j-1][0]+map[j-2][0];
					map[j][1] = map[j-1][1]+map[j-2][1];
			}
			
			System.out.println(map[N][0]+" "+map[N][1]);
		}

	}// main

}// class-end