프로그래머스 피보나치 수(Java)

사이트명 : 프로그래머스(Programmers)

문제명 : 피보나치 수

언어 : 자바(Java)

 

일단 피보나치 수를 풀기에 앞서서 문제 개념을 좀 알고 넘어가야 하는데

n은 항상 2 이상으로 들어오며

F(0) -> 0 F(1) -> 1 고정이다

 

F(2) -> F(0) + F(1) = 0 + 1

F(3) -> F(1) + F(2) = 1 + 1

....

 

이런 식으로 이어진다

n 값이 10이라면 F(8) + F(9)를 해서 주면 되는 것이다

 

여기에 함정이

문제 설명을 이상하게 해놔서

정답을 제대로 뽑아내려면

 

만약 n이 10일 경우

(F(8) % 1234567) + (F(9) % 1234567)

F(n) 값도 % 1234567을 해서 return 시켜야 한다

 

내 풀이방법은 아래와 같은데

 

일단 F(n)을 구하려면

F(n-2) + F(n-1) 을 해주면 된다는 것을 깨달은 순간

 

for 문을 돌리면서 1부터 n까지의 피보나치 수를 계속 구해주면 된다

여기에 %1234567 을 계속 해줘야 테스트 7번부터 틀리지 않고 옳게 처리되는데

문제 설명을 이상하게 해놔서

 

대부분은 맨 마지막에만 % 1234567을 했을 것이다

그 전의 피보나치 수를 구하는 과정에도 % 1234567을 해줘야 했는데

유의해서 풀어야 한다는 개뿔

 

문제를 저렇게 써놓으면 전 과정에 %1234567이 들어가는지 어떻게 알겠나

 

마지막으로 프로그래머스에 바로 적용 가능한 코드는 아래와 같다

 

class Solution {
  public int solution(int n) {
		int arr[] = new int[n];
		
		for(int i = 0; i<n; i++) {
			
			if(i == 0) {
				arr[i] = 0;
			} else if(i == 1) {
				arr[i] = 1;
			} else {
				arr[i] = (arr[i-2] % 1234567) + (arr[i-1] % 1234567); 
			}
			
		}
		
		int answer = ( arr[n-1] + arr[n-2] ) % 1234567;
		
		return answer;
  }
}