[자바] 피보나치 수

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

프로그래머스

 

피보나치 수를 재귀로는 풀어봤지만, 시간초과가 났다. 그래서 for문으로 구현하려고 했는데, 어떻게 값을 더해나가지 고민했지만, 답이 나오지 않았다.

그래서 방법은,, 이전값을 배열에 저장해놓고, dp[n]번째에, dp[n-1]+dp[n-2]를 저장하는 메모리제이션 방식으로는 풀면 해결이 되었다.

같은 문제라도 여러 풀이로 풀 수 있도록 생각을 유연하게 해야겠다. 

 

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