[ 프로그래머스, Lv2 ] [ JAVA ] 멀리뛰기 - DP

 

 

프로그래머스

 

 

 

안녕하세요 ( •̀ ω •́ )✧

 

오늘은 프로그래머스의 Level 2 문제 멀리뛰기를 풀어보았습니다 !

 

멀리뛰기 문제는 DP로 해결할 수 있었는데, DP에 대해 지난 글에서 다뤘기 때문에 설명이 필요하신 분들은 참고하시면 좋을 것 같습니다.

 

 

[ 알고리즘 ] DP(Dynamic Programming) - 동적계획법

 

 

<< 문제 >>

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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 이하인 정수입니다.

 

 

문제를 간단히 요약해보자면

 

1이상 2000이하인 정수를 입력받습니다.

입력받은 값을 2와 1의 합으로 표현하고, 가능한 모든 조합의 갯수를 구하고 이때 1234567로 나눈 나머지를 출력합니다.

 

 

프로그래머스에 제출한 코드는 다음과 같습니다.

 

class Solution {
    public long solution(int n) {
        long[] answer = new long[n+2];

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

        return answer[n];
    }
}

 

 

문제의 답을 1부터 구하면

 

1을 입력했을 땐 1이, 2를 입력했을 땐 2, 3을 입력했을 땐 3, 4를 입력했을 땐 5로

 

1, 2, 3, 5, 8, 13의 형태로 반복되는 패턴을 확인할 수 있었습니다.

 

따라서 dp[n] = dp[n-1] + dp[n-2]를 구하고 출력 조건인 1234567의 나머지를 출력하도록 합니다.

 

 

 

 

덧붙이자면...

만약 1을 입력했을 때, answer의 크기는 2가 되는데 answer[2]가 범위를 벗어나는 오류가 발생하여

long[] answer = new long[n+2]로 생성해줍니다.