프로그래머스 멀리 뛰기(lvl2) 풀어보기

문제링크

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

프로그래머스

 

---

문제 핵심

• 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
  (1칸, 1칸, 1칸, 1칸)
  (1칸, 2칸, 1칸)
  (1칸, 1칸, 2칸)
  (2칸, 1칸, 1칸)
  (2칸, 2칸)
• 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요

---

알고리즘

-피보나치수열이용

---

코드

 public static  BigInteger solution(int n) {

        BigInteger answer = BigInteger.valueOf(0);

        int index=0;

        BigInteger[] arr=new BigInteger[2];

        arr[0]=BigInteger.valueOf(0);

        arr[1]=BigInteger.valueOf(1);

        while (index<n) {

            answer=arr[0].add(arr[1]);

            arr[0]=arr[1];

            arr[1]=answer;

            index+=1;

        }

        answer = answer.mod(BigInteger.valueOf(1234567));

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt피드백

-네 알고리즘 자체는 정확해.

피보나치를:

현재 = 이전 두 값의 합

으로 n번 계산하니까 반복 횟수 기준으로는 **O(n)**이고, 이 문제에서 충분히 좋은 접근이야.

문제는 원본 피보나치 숫자를 요구하지 않고 나머지만 요구한다는 거야.

그러면 아래공식 :

(a + b) % M
=
((a % M) + (b % M)) % M

을 이용해서 매번 나머지만 저장하는 게 더 효율적이야.

answer = (arr[0] + arr[1]) % 1234567;

그러면 숫자가 절대 커지지 않아.

 

 

 

---

배운점느낀점

-처음에 딱보고 헐 dfs? 써야하나 하고 

고민 했던 문제 였다 근데 그냥 혹시 

결과가 소수들만 있나 해서 12345 해보니

12358? 더해보니 1321 ?? 이거 피보나치 수열이잖아?

이게 보였다 그래서 어이없게 쉽게 풀었다