[BOJ] 2748. 피보나치 수 2 (Java)

문제 링크 / level: Silver V

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

2748번: 피보나치 수 2

 

 

내가 생각한 풀이

앞에서 [2747.피보나치 수] 문제를 풀어보았다.

https://ming-jee.tistory.com/9

[BOJ] 2747. 피보나치 수

이번에도 똑같이 피보나치 수를 구하는 문제인데 앞에서 풀었던 문제보다 input으로 주어질 수 있는 n의 값이 두 배 늘어났다.

[2747.피보나치 수]에서는 n의 범위가 45까지였는데, 이번에는 90까지로 늘어난 것이다. 이와 동시에 난이도도 브론즈에서 실버로 떡상했다^_^

 

문제의 핵심 (출처: BOJ)

이 문제를 재귀함수로 구현했다가는 꼼짝없이 터져버리고 말 것이다. 또한, 앞에서는 사실상 int type으로 구현해도 상관없었는데 이번에는 n=90일 경우에 int type의 범위를 가뿐하게 넘어가는 결과값이 나오므로 이번에야말로 반드시 long type으로 구현을 해줘야한다. (참고로 90번째 피보나치 수의 값은 2880067194370816120이다.)

int type으로 구현할 경우 이렇게 터진다.

앞에서 짠 코드가 여기에서도 통할까?

알아보자~~!

// 핵심 코드
private static long fibo2(int n) {
	if(n<=1) {return n;}
	if(memo[n]!=0) {return memo[n];}
	else {
		return memo[n] = fibo2(n-1) + fibo2(n-2);
	}
}

[2747.피보나치 수] 코드에서 바뀐건 하나도 없고 그냥 문제 번호에 맞춰서 fibo1을 fibo2로 이름만 변경해줬을 뿐이다.

어차피 앞에서 이미 재귀함수가 아닌 메모이제이션으로 구현했기 때문에 스무스하게 통과할 것이라고 예상했다.

그리고 성공!!

이번에도 논리는 같다.

memo 배열을 이용할 것이고, 만약 계산한 적 있다면 해당 인덱스(n번째 피보나치 수에 해당함)에 있는 원소의 값이 0이 아닐 것이기 때문에 그걸 바로 return해주면 되는거고 만약 계산한 적이 없다면 피보나치 수열의 공식인 f(n) = f(n-1) + f(n-2)를 이용해서 값을 구해준 뒤에 그 값을 memo 배열에 업데이트 시켜주면 되는 것이다.

 

즉, memo 배열의 역할은

1. 계산한 적 있는지 없는지 체크 (원소의 값이 0인지 아닌지로 판단)

2. 계산한 후 값을 저장할 용도

참고로 memo 배열의 사이즈는 input 값보다 하나 더 크게 해서 인덱스 1의 원소가 곧 1번째 피보나치의 수가 될 수 있도록 했다. 예를 들어, memo 배열에서 인덱스가 10인 원소값은 곧 10번째 피보나치 수이다.

0

1

1

2

3

5

8

13

21

34

55

0번째 피보나치의 수는 0, 1번째 피보나치의 수는 1, ... , 10번째 피보나치의 수는 55 (보통 앞에 1~2개 정도는 문제에서 알려줌!)

이러면 안 헷갈리기도 하고 ㅎㅎ 참 쉽죠?😏

 

 

- 피보나치 수 시리즈는 계속된다, to be continued... -