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

[ 피보나치 수 ]

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

 

입출력 예

n	return
3	2
5	5

 

입출력 설명

 피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

 

[ 풀이 ]

public class Solution {
    
    int temp;
    int before;
    int answer;
    int a = 1234567;
    
    public int solution(int n){
        
        // 0번째는 0, 1번째는 2이기에 1이하는 n을 반환.
        if(n <= 1) return n;
        
        // 2번째 값부터 재귀함수로 구하기 때문에 구하지 않은 1번째 값인 before에 1을 넣어주고 시작.
        before = 1;
        
        for(int i = 2; i <= n; i++){
            answer = (temp + before) % a; // (n - 2) + (n - 1)
            temp = before; // 더하고 다음 값을 위해 before은 (n - 2)가 된다. 
            before = answer; // 더하고 다음 값을 위해 이번 answer은 (n - 1)이 된다.
        }    
        
        return answer % a;
    }
}

public class Solution {

    public int solution(int n){
        int[] arr = new int[n + 1];
        // 피보나치 수열의 0번째, 1번째 값은 0, 1이기에 0, 1번째 배열에 0,1을 넣고 시작.
        arr[0] = 0;
        arr[1] = 1;
        
        if(n <= 1) return arr[n];

        for(int i = 2; i <= n; i++){
        	// (n - 2) + (n - 1)을 arr[n]에 삽입.
            arr[i] = (arr[i - 2] + arr[i - 1]) % 1234567;
        }
        
        return arr[n];
    }
}

 

 피보나치 수는 첫번째와 두번째는 1이고, 그 뒤의 모든 값은 바로 앞 두 개의 값을 더한 값인 수열이다.

  

그래서 배열을 그냥 전전 값이랑 전 값을 넣어놓은 배열을 꺼내서 더하면 끝이기 때문에 매우 쉽다.