[프로그래머스 Lv.2] 피보나치 수.java

📖 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12945

문제 설명

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 

예를들어 

• F(2) = F(0) + F(1) = 0 + 1 = 1
• F(3) = F(1) + F(2) = 1 + 1 = 2
• F(4) = F(2) + F(3) = 1 + 2 = 3
• F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

---

✏️ 풀이

[실패 1] 런타임 에러

재귀함수로 풀면 시간초과로 실패함. 배열을 만들어 해당 값만 저장해 해결

 

[성공] fibo 배열을 만들어 피보나치 수열을 저장한다.

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

//	public static void main(String args[]) {
//		System.out.println(solution(5));
//	}
}

---

문제 보자마자 아는 코드(재귀함수)로 적으면서 음~ 무조건 런타임에러 뜨겠군~ 했는데 진짜로 런타임 에러 나 줌 ~,~

그래서 포문 돌면서 피보 수열만 저장하는 걸로 바꾸니 바로 성공했습니다요.. 

1234567으로 나누란 소리는 왜했는지 의문.........

첨에는 정수 타입이라 그런가 생각했는데 최대 100,000이면 충분한 거 아닌가...... 나중에 찾아봐야지