[코딩테스트] 백준(BAEKJOON) - 피보나치 함수(Java, 1003번)

안녕하세요.

오늘풀어본 문제는 제목은 간단하지만 의외로 이상한곳에 간단하지 않았던 문제

피보나치 함수입니다. DP의 대표적 문제로 피보나치라고하면 금방 떠오르실거라 생각됩니다.

 

그러나 백준의 자료입력받는 방식이 당최 적응이 안되네요.

이거때문에 몇 번을 틀렸는지 모르겠습니다.

 

자 그럼이제 시작해보겠습니다.

 

먼저 문제입니다.

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

1003번: 피보나치 함수

 

다음은 제가 작성한 코드입니다.

 

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

public class Main {
		public static void main(String[] args) throws NumberFormatException, IOException {	
		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		
		int count=Integer.parseInt(bf.readLine());
		for(int j=0;j<count;j++)
		{
			int number=Integer.parseInt(bf.readLine());
			int[] fib1=new int[41];
			int[] fib0=new int[41];
			
			fib0[0]=1;
			fib1[0]=0;
			
			fib0[1]=0;
			fib1[1]=1;
			
			for(int i=2;i<=number;i++)
			{
				fib0[i]=fib0[i-1]+fib0[i-2];
				fib1[i]=fib1[i-1]+fib1[i-2];
					
			}
			System.out.println(fib0[number]+" "+fib1[number]);
						
		}	
	}

}

기존의 피보나치와 로직은 비슷합니다. 그러나 이번에는 0일경우와 1일 경우의 피보나치 수열을 각각 계산한다는데 아이디어가 있다고 보시면 되겠습니다.

 

또한 다른이들의 풀이를 보니 N-1항의 0의 갯수와 1의 갯수를 더해 N번째의 1의갯수를 찾던데 이런 아이디어도 있다는점 참고해 주시면 되겠습니다.

 

이번에는 간단한 만큼 마지막으로 제 풀이 남겨놓고 마무리하겠습니다.

 

감사합니다. :D