프로그래머스[12914] - 멀리 뛰기(lv2)

문제설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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가지 방법으로 멀리 뛸 수 있습니다.

문제해결 keyPoint

1. 4가지 일때, 3가지 일때, 2가지 일때, 1가지 일때 손으로 알아볼 수 있는 가짓수들을 구해보고 연관된 규칙을 찾아보자.

20220912 1차시도

우선 문제를 관심하세 따라서 분리?.. 한건 좀 나은듯, 이런 습관을 계속 길러야겠다.

 

나머지는 상관없고 결국 가짓수를 구하는 메인 비지니스로직을 어떻게 짤지 몰라서 시간을 초과했다.

중복순열/조합을 이용해서 풀 수 있지 않을까? 생각했는데, 일단 그 수학적 지식을 받아드리는데 시간이 초과 ㅎ/... 그래서 풀이를 참고해보자

    private final long DIVISOR = 1234567; //나눗셈 제수
    public Long solution(int n){
        /**
         * 1. 칸은 한번에 1칸 또는 2칸을 뛸수있다.
         * 2. 멀리뛰기에 사용될 칸의 수 n
         * 3. n칸을 뛸수 있는 가짓수를 구한다.
         * 4. 구한 값에 1234567을 나눈 나머지를 반환한다.
         * 5. 가짓수를 구하는 방법으로 중복순열, 조합을 생각했는데, 이해가 잘 되지 않아 풀이로 넘어간다.
         */
        long answer = 0L;
        
        // 멀리뛰기 가짓수에 1234567을 나눈 나머지를 구한다.
        answer = this.getCountJumpings(n) % DIVISOR ;

        return answer;
    }

    /**
     * n에 대한 뛰기 방법을 구한다.
     * @param n
     * @return
     */
    public int getCountJumpings(int n){
        int result = 0;
        int min = n/2 ==0 ? n/2 : n/2+1;

        for(int i = min; i<=n; i++){
            result += this.getPermutation(i);
        }
        return result;
    }

    public int getPermutation(int n){
        int permutationResult = 0;
        //TODO : 중복순열? 조합?...
        return permutationResult;
    }

20220912 2차시도(풀이참고)

ㅁㅊ... ㅈㄴ 간단했다... 하.. 이게 간단한 DP라던데... 

너무 수학적 알고리즘?..에 같혀서 그랬던 것인가....

 

대박이담..

 

의외로 간단한 규칙을 볼수있었을탠데, 너무 수학적 알고리즘에 시야가 같혔던것 같다.

class Solution {
    public long solution(int n) {
        /**
         * 1. n번째 칸의 가짓수는 n-1,n-2번째 칸의 합과 같다.
         * 2. 그러므로 시작값 1칸,2칸일때를 미리 구하고
         * 3. 문제에서 주어진 최대 칸의 갯수까지 반복문을 통해 가짓수를 구한다. (배열에 저장)
         * 4. 배열[n]에 해당하는 값에서 1234567을 나눈 나머지를 반환한다.
         * 5. 최댓값 까지 구하지 않아도 n까지만 구해놔도 될듯 하다.
         */
        int[] dp = new int[n+1];
        dp[1] = 1;
        if(n>=2){
             dp[2] = 2;
        }
        if(n>=3){
            for (int i = 3; i < n+1; i++) {
                dp[i] = (dp[i - 2] + dp[i - 1]) % 1234567;
            }
        }
        return dp[n]*1L;
    }
}

기분좋당 ㅋㅋ

refs

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

프로그래머스

https://blog.naver.com/jjangting/222840406062

확률과통계 경우의수 순열 조합 중복순열 중복조합 개념정리

https://zzang9ha.tistory.com/138

프로그래머스[Java] - 멀리 뛰기(DP)