[PS/JS] 프로그래머스 - 멀리 뛰기

Pakxe·2023년 4월 26일

JavaScript ps 프로그래머스

PS

목록 보기

11/16

문제

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12914

풀이

n칸이 주어질 때 1칸, 2칸씩 점프할 수 있는 효진이가 몇 가지 수로 n칸에 도달할 수 있는지 세는 문제이다.
일단 무슨 문제인지 파악하기 위해 하나씩 값을 대입하며 풀어보자.

n = 1

일단 하나씩 풀어보자. n은 1이상이라고 했으니까, n=1일 때는 몇 가지일까? 1칸만 뛰면 되니까 1가지 방법이 존재한다.

n = 2

n=2일 때는 몇 가지일까?

1 + 1

2

이렇게 2가지 방법이 존재한다. 일단 간단하게 1칸+1칸은 이 2칸이 분해되어 나온 가짓 수라고 생각해보자.

n = 3

n=3일 때는 몇 가지일까?

1 + 1 + 1

1 + 2

2 + 1

이므로 총 3가지 방법이 존재한다. 이때 1칸을 먼저 뛰는 1칸+1칸+1칸, 1칸+2칸 방법에 집중해보자. 둘다 1칸을 먼저 뛰고, 1칸+1칸, 2칸을 뛰었다. 이는 n=2일 때의 뛰는 방법과 동일하다. 이게 무슨말이냐면, n=3은 n=1+2라는 관점에서 볼 수도 있다. 그렇게되면 1칸을 일단 뛰고 남은 칸수인 2칸을 어떻게 뛸지는 n=2일때 구했던 것들을 사용해도 된다는 의미이다. 그리고 n=3을 뛰는 3번째 방법 또한 2칸+1칸이므로, 2칸을 뛰고 남은 한칸을 n=1일때 구했던 방법 수를 사용할 수 있다. 아직 n이 작아서 와닿지 않을 수 있으니 계속해보자.

n = 4

n=4일 때는 몇 가지일까?

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

2 + 2

1, 2, 3번 방법을 잘 보자. 1칸을 제일 먼저 뛰고 1+1+1, 2+1, 1+2 를 추가해서 4칸을 뛰었다. 그런데 이 1+1+1, 2+1, 1+2방법은 n=3일때의 3가지 방법과 동일하다. 결국 n=4를 n=1+3의 관점에서 본 것과 똑같다. 결론적으론 1칸을 뛰고 남은 n=3(3칸을 뛰는 방법개수)이 1칸을 먼저 뛰었을 때의 가짓수이다.

나머지 4, 5번도 봐보자. 2칸을 제일 먼저 뛰고 1+1, 2 를 추가해서 4칸을 뛰었다. n=4가 n=1+3인 걸 눈치챘다면.. n=2+2또한 가능하다고 생각할 수 있다.(여기까지 생각이 잘 흘러갔다면 성공)
n=2를 보면 방법이 1+1, 2로 두가지 존재한다. 그렇게되면 결국, 2칸을 뛰고 남은 n=2(2칸을 뛰는 방법 개수)이 2칸을 먼저 뛰었을 떄의 가짓수이다.

n=4는 총 5개의 방법이 나왔다. 그렇다는건 1칸을 먼저 뛸때의 가짓수 + 2칸을 먼저 뛸떄의 가짓수가 결국 n=4의 총 가짓수라고 결론지을 수 있다.

n = 5

계속 했으니까 간단하게 말하자면,
n=5 또한 똑같은 방법으로 가짓수를 구할 수 있다. n = 5 = 1+4 = 2+3 이므로 1칸 + n=4, 2칸 + n=3을 구해서 n=5의 가짓수를 구할 수 있는 것이다.

점화식을 세워보자

이제 어느정도 규칙을 알았으니 점화식을 세울 수 있을 것 같다.
뛰는 방법은 1칸, 2칸으로 2가지 존재한다.

뛰는 방법의 개수를 반환하는 함수를 jump라고 한다면, jump(4) = jump(3) + jump(2)로 jump(4)를 구할 수 있다.

이걸 n칸으로 확장한다면, jump(n) = jump(n-1) + jump(n-2)로 점화식을 세울 수 있다.

(만약 주인공이 1칸, 2칸이 아닌 3칸도 한번에 뛸 수 있다면 점화식은 jump(n) = jump(n-1) + jump(n-2) + jump(n-3)이 될 수도 있었겠다.)

정답 코드

function solution(n) {
    return jump(n);
}

const jump = n => {
    const dp = new Array(n).fill(0); // n개의 길이 배열 dp 생성
    
    dp[1] = 1; // 1칸
    dp[2] = 2; // 1칸1칸, 2칸
    
    for(let i = 3; i <= n; i++) {
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567; // jump(n) = jump(n-1) + jump(n-2)
    }
    
    return dp[n];
}