[ 알고리즘 ] 코딩 - Programmers - 피보나치수.java

---

문제 링크

programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

---

* 프로그래머스 - Level 2 - 피보나치 - 일반 수학(DP)

기본적인 DP로 풀었다.

위 이미지가 피보나치인 동시에 정답

 

---

< 로직 >

* 피보나치수를 계산하여 그대로 출력한다!

* 엄청나게 큰 숫자가 다루어 지므로 각 숫자마다 %1234567의 나머지 연산을 한다

* 중간에 계산할때도 mod연산을 해줘야한다.

* 자칫 잊으면 오답이 나오므로 조심!

---

class Solution {
    public int solution(int n) {
     		int mod = 1234567; // 충분히 큰 수
	    	int[] fibo = new int[n+1];
	    	
	    	fibo[0] = 0; // 시작
	    	fibo[1] = 1; // 시작
	    	
	    	for(int i = 2; i <= n; i++) {
	    		fibo[i] = fibo[i-2]%mod + fibo[i-1]%mod; // 피보나치 계산
	    	}
	    	
	        int answer = fibo[n]%mod;
	        return answer;
    }
}