[백준] 1003번 피보나치 함수 - JAVA

---

• 문제
• 풀이

---

문제

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제 내용은 지적 재산 보호 차원에서 가져오지 않고 풀이만 공유드리도록 하겠습니다.

---

풀이

 제 풀이가 무조건적으로 맞는 것도 최적의 답변도 아니지만, 이런 풀이도 있다는 차원에서 작성해 보며, 좀 더 나은 방법이 있다면 이야기해 주셔도 도움 될 것 같습니다.

 

 풀이에 도움이 될 만한 피보나치수열에 대한 설명입니다.

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

 단순하게 주어진 피보나치 수를 함수로 만들어서 재귀로 띄었다가 어마어마한 실패만 출력되었습니다. (ㅠ.ㅠ)

재귀함수에 따른 메모리 / 시간 초과

 그래서 엑셀에 0부터 10까지 적어두고 0과 1의 개수를 적어보니 어느 정도 규칙성이 보이기 시작했습니다.

0부터 10까지 주어졌을 때 0과 1의 개수

 1행이 주어진 숫자이고 2행이 0의 개수, 3행이 1의 개수일 때, 0과 1을 제외한, 2부터는 앞의 개수와 앞의 앞의 개수의 합이 현재 값의 결과가 됨을 확인할 수 있었습니다.

 

ex) 주어진 값 4의 0의 개수 = 3의 0의 개수 [1] + 2의 0의 개수 [1] = 2

ex) 주어진 값 8의 1의 개수 = 7의 1의 개수 [13] + 6의 1의 개수 [8] = 21

 

import java.util.Scanner;

/**
 * 백준 문제 1003 - 피보나치 함수
 * @author royzero
 *
 */
public class Main {
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
		
		// Step. 반복 횟 수 입력
		int count = in.nextInt();
		
		// Step. 반복 횟 수 만큼 처리
		for(int i = 0; i < count; i++){
			// Step. 정수 입력
			int n = in.nextInt();
			
			if(n == 0)		System.out.println("1 0");
			else if(n == 1)	System.out.println("0 1");
			else{
				int[] resultZero = new int[n];
				int[] resultOne  = new int[n];
				resultZero[0] = 0;
				resultZero[1] = 1;
				resultOne[0]  = 1;
				resultOne[1]  = 1;
				for(int idx = 2; idx < n; idx++){
					resultZero[idx] = resultZero[idx - 1] + resultZero[idx - 2];
					resultOne[idx] = resultOne[idx - 1] + resultOne[idx - 2];
				}
				System.out.println(resultZero[n-1] + " " + resultOne[n-1]);
			}
		}
		
		in.close();
	}
}

제출 결과