[백준] 1003번 피보나치함수 (DP_JAVA)

무난하게 푼 문제!

그렇게 어렵지는 않았다.

 

---

문제

 

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

1003번: 피보나치 함수

 

---

설계

 

알고리즘 설계 [접근방법]  : DP

숫자가 주어질 때, 이 숫자가 결국에는 0과 1이 얼마나 있는지 개수를 세어야 하는 문제이다.

숫자의 범위가 40보다 작으니 배열을 생성하여 dp로 가능할 것이라 생각했다.

DFS보다 배열로 푸는 것이 훨씬 시간복잡도가 적으니 무난히 통과한 문제다.

 

풀이 과정

 1.

최대 40의 숫자가 입력될 수 있으므로 배열 2개를 41크기로 생성한다.

zeroArr은 0이 몇 개 있는지 그 값을 담을 배열이고, oneArr은 1의 개수를 셀 배열이다.

 

2.

2부터 41까지 반복문을 돌며 피보나치를 해준다.

2로 예를 들면, oneArr[1] + oneArr[0]의 값이 2가 가진 1의 개수다. 그러므로 oneArr[2]에 값을 저장하면되고, zeroArr도 마찬가지다.

 

3.

그리고 idx를 입력 받은 후 zeroArr[idx]와 oneArr[idx]에 있는 값을 출력하면 된다.

 

 

---

코드

 

import java.util.Scanner;

public class Test_1003_피보나치함수 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] zeroArr = new int[41];	//0 개수 배열
		int[] oneArr = new int[41];	//1 개수 배열
		
		zeroArr[0]=1;	
		zeroArr[1]=0;
		oneArr[0]=0; 	
		oneArr[1]=1;
		
		for(int i=2; i<41; i++) {
			zeroArr[i]=zeroArr[i-1]+zeroArr[i-2];
			oneArr[i]=oneArr[i-1]+oneArr[i-2];
		}
		
		
		int n = sc.nextInt();
		for(int i=0; i<n; i++) {
			int idx = sc.nextInt();
			
			System.out.println(zeroArr[idx] +" "+ oneArr[idx]);
		}
		
	}
}

 

 

(❁´◡`❁)

끝!