[프로그래머스] 피보나치

문제

 

 

 

분석

피보나치를 구현해서 풀면된다.

하지만 문제 중 2이상의 n 이 입력이 되었을때 N 번째 피보나치 수를 1234567 로 나눈 나머지 리턴...

조건이 불친절하고 명확하지가 않다.

그래서 여러가지 시도를 해봤다

 

1. 구한 피보나치 마다 %1234567 을 하란것인가?

2. 전체를 구한 값에서 %1234567 을 하란말인가?

 

1번이 맞았다.

 

뭔가 효율성 검사도 할지 몰라서 DP 를 이용해서 풀었다.

피보나치는 반복된 값이 나오기 때문이다.

 

구현

class Solution {
    
    private long []dp;
   
    
    public long fibo(int n) {
        if(dp[n] != 0) {
            return dp[n];
        }
        dp[n] = (fibo(n-1) + fibo(n-2)); 
        return dp[n] % 1234567;
    }
    
    
    public int solution(int n) {
        int answer = 0;
        dp = new long[1000001];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        
        long answer1 = fibo(n);
        answer = (int)answer1;
        return answer;
    }
}

 

 

결과

 

 

 

 

문제링크: https://programmers.co.kr/learn/courses/30/lessons/12945

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