[알고리즘] 코딩테스트 연습(연습 문제) - [JavaScript] 멀리 뛰기

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

프로그래머스

본 포스팅에서 다루는 문제는 위 프로그래머스 링크를 통하여 문제 확인 및 풀이가 가능합니다!

 

 

1. 문제 풀이

 본 문제는 동적 계획법(Dynamic Programming)으로 풀이 가능한 문제들 중 가장 베이직한 경우로 볼 수 있습니다. 효진이가 n칸의 계단을 오르는 방법의 총 가짓수를 bottom-up 방식으로 구하는 것이 문제 풀이에서 가장 중요한 포인트입니다.

 또한, 동적 계획법을 풀이할 때 가장 중요한 것은 점화식을 구하여 recursive case를 만드는 것입니다. 효진이가 n번째 칸 계단에 오르는 방법은 총 2가지 입니다. 첫 번째는 n-1번째 칸에서 1칸을 오르는 경우, 두 번째는 n-2번째 칸에서 2칸을 오르는 경우입니다.

 

 

2. 정답 코드

function solution(n) {
    const dp = new Array(n + 1).fill(0);     
    // base case
    dp[1] = 1;
    dp[2] = 2;
    
    // recursive case
    for (let i = 3; i <= n; i++)
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;

    return dp[n];
}

 동적 계획법을 적용한 코드는 크게 두 가지 영역으로 나눌 수 있습니다. base case와 recursive case로 말이죠. 위에서 말한대로 n번째 칸에 도착하는 방법은 n-1번째 칸에서 1칸을 올라오거나 n-2번째 칸에서 2칸을 올라오는 것뿐이므로 (n번째 칸을 오르는 경우의 수) = (n-1번째 칸을 오르는 경우의 수) + (n-2번째 칸을 오르는 경우의 수)임을 알 수 있습니다.

 base case와 recursive case를 코드로 작성하는 것은 크게 어려움이 없는 문제였고 동적 계획법에 대한 기초적인 이해 여부를 확인하는 문제 정도로 생각됩니다.