[Java/알고리즘] 프로그래머스 멀리 뛰기 피보나치 수열

문제 설명

---

프로그래머스

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

입출력 예

nresult

4	5
3	3

입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

문제 풀이

---

DP 점화식으로 풀이 - 프로그래머스 해당 문제 질문하기 글 참고

 

n번째 칸으로 뛰는 방법의 수는

[n-1]번째 칸으로 뛰는 방법 수 + [n-2]번째 칸으로 뛰는 방법의 수가 되며, 이는 피보나치 수열과 동일하다.

class Solution {
    public long solution(int n) {
        long[] memo = new long[2001];
        memo[1] = 1;
        memo[2] = 2;

        for (int i = 3; i <= n; i++) {
            memo[i] = (memo[i - 1] + memo[i - 2]) % 1234567;
        }

        return memo[n];
    }
}

 

나는 아래 표와 같이 n 입력 값에 따른 멀리 뛰기 조합을 구해보고 싶었다.

1	2	3	4	5
n = 1 [1] result = 1	n = 2 [1,1] [2] result = 2	n = 3 [1,1,1] [1,2] [2,1] result = 3	n = 4 [1,1,1,1] [1,2,1] [1,1,2] [2,1,1] [2,2] result = 5	n = 5 [1,1,1,1,1] [2,1,1,1] [1,2,1,1] [1,1,2,1] [1,1,1,2] [2,2,1] [2,1,2] [1,2,2] result = 8

BFS를 사용하여 구현 문제 통과는 시간 초과 때문에 되지 않는다.

public static int solutionQ(int n) {
        Queue<ArrayList<Integer>> q = new LinkedList<>();
        int result = 0;
        q.add(new ArrayList() {{add(1);}});
        q.add(new ArrayList() {{add(2);}});

        while(!q.isEmpty()){
            ArrayList<Integer> poll = q.poll();
            int total = poll.stream().mapToInt(Integer::valueOf).sum();
            System.out.println("=============");
            System.out.println("poll = " + poll);
            System.out.println("total = " + total);
            System.out.println("=============");
            if(total == n){
                result++;
                continue;
            }

            // 1 or 2칸만 이동 가능
            for (int i = 1; i < 3; i++) {
                ArrayList<Integer> next = null;
                if(total + i <= n) { // n이 합계 이상
                    next = new ArrayList<>(poll); // 깊은 복사 / next = poll 은 같은 주소값을 바라봄 - 값이 동시 변경
                    next.add(i);
                    System.out.println("next = " + next);
                    q.offer(next);
                }
            }
        }
        System.out.println("result = " + result);
        return result % 1234567;
    }