[001] 피보나치 수 구하기

피보나치 수 구하기는 제일 기초적인 문제 중 하나로 이 문제의 경우 일정 크기 이상의 수가 입력되었을 때 (큰 수 받았을 경우) 처리를 어떻게 구할 수 있냐의 문제이다.

 

엄청 오랜만에 하는 문제이다보니 우선 간단하게 피보나치 수를 구하는 방식을 대입해서 문제를 풀었다.

 

        int answer = 0;
        int num = 3;
        Long [] res = new Long[num];
        int ret = 0;

        res[0] = 1L;
        res[1] = 1L;

        for(int i = 2; i < num; ++i){
            res[i] = res[i-1] + res[i-2];
        }
        ret = Math.toIntExact(res[num - 1] % 1234567);

        System.out.println(ret);

 

처음에는 int로 사용하다가 어...? 하면서 급하게 long으로 변경한 흔적을 보라

 

여기에서 문제가 생긴 건 그럼에도 인하고 연산의 크기가 크고 그렇다보면 처리속도가 엄청나게 느려진다는 것이다. 물론 수가 더 커지면 long 안에서도 감당하지 못할 것도 있음!

어떻게 하지 하고 고민하다 모듈러의 성질이라는 걸 기억해냄. 

 

어차피 1234567을 나눈 나머지를 구하는 문제이기 때문에 애초에 그 나머지만 res에 저장하면 된다는 거다

그래서 수정을 했다.

 

 public void t0001(){
        int answer = 0;
        int num = 3;
        Long [] res = new Long[num];
        int ret = 0;

        res[0] = 1L;
        res[1] = 1L;

        for(int i = 2; i < num; ++i){
            res[i] = (res[i-1] + res[i-2]) % 1234567;
        }
        ret = Math.toIntExact(res[num-1]);

        System.out.println(ret);
    }

 

여기에서 이제 애초에 나눈 만큼의 나머지이기 때문에 그 수가 크지 않을 것이다. 즉, long까지 가지 않아도 충분히 연산이 가능하기 때문에 long 타입을 int 로 다시 변경했다.

 

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

 

완성 '/-')/

 

너무 오랜만에 하는 연습문제라 과한 수에 대해서는 생각하지 않았는데 거의 재활운동 하는 느낌이다... ㄴㅇㄱ