[ 프로그래머스 멀리 뛰기 (Lv3) ] (C++)

프로그래머스의 멀리뛰기(Lv3) 문제이다.

[ 문제풀이 ]

하나의 수식을 이용해서 문제에 접근해보자.

F[A] = B 라는 수식을 사용해볼 것인데, 이 수식의 의미는 "A번칸 까지 갈 수 있는 방법은 총 B가지 방법이 있습니다." 를 의미한다.

그럼, N = 4 인 경우(4칸이 주어졌는 상황)를 예시로 진행해보자.

가장 먼저, 1번칸까지 갈 수 있는 방법은 몇 가지가 있을까 ??

시작점에서 1번칸 까지 1칸 뛰면 1번칸 까지 갈 수 있다.

이 방법 외에는 1번칸 까지 갈 수 있는 방법은 없다.

F[1] = 1

2번칸 까지 갈 수 있는 방법은 몇 가지가 있을까 ??

방법의 수를 계산하기 전에 먼저 갈 수 있는 방법을 모두 적어보자.

1. 시작점 - 1번칸 - 2번칸

2. 시작점 - 2번칸

위와 같이 2가지 방법이 있다.

F[2] = 2

3번칸 까지 갈 수 있는 방법을 모두 적어보자.

1. 시작점 - 1번칸 - 2번칸 - 3번칸

2. 시작점 - 1번칸 - 3번칸

3. 시작점 - 2번칸 - 3번칸

위와 같이 3가지 방법이 있다.

F[3] = 3

마지막으로 4번칸 까지 갈 수 있는 방법을 모두 적어보자.

1. 시작점 - 1번칸 - 2번칸 - 3번칸 - 4번칸

2. 시작점 - 1번칸 - 3번칸 - 4번칸

3. 시작점 - 2번칸 - 3번칸 - 4번칸
4. 시작점 - 1번칸 - 2번칸 - 4번칸

5. 시작점 - 2번칸 - 4번칸

F[4] = 5

위와 같은 방식으로 구한다면, 4칸이 주어졌을 때, 갈 수 있는 방법은 총 5가지가 있다는 것을 알 수 있다.

그런데, 언제까지나 이렇게 하나하나 구할 수는 없으니, 보다 일반화된 이야기를 한번 해보자.

위에서 계산한 "마지막 4번칸 까지 갈 수 있는 방법들"을 보면서 이야기를 해보자.

위의 5가지 방법들 중에서, 1번 2번 3번 방법들에는 한 가지 공통점이 있다.

1. 시작점 - 1번칸 - 2번칸 - 3번칸 - 4번칸

2. 시작점 - 1번칸 - 3번칸 - 4번칸

3. 시작점 - 2번칸 - 3번칸 - 4번칸

바로 3번칸을 거쳐서 간다는 것이다. 그리고 그 과정들을 보게되면,

1번칸 - 2번칸 - 3번칸

1번칸 - 3번칸

2번칸 - 3번칸

으로 가는 3가지 방식이 있는데, 이 3가지 방식은 우리가 기존에 계산했던 "3번칸 까지 갈 수 있는 방법들" 에 속하는 것이다.

즉, 4번칸으로 가기 위해서는, 3번칸으로 간 후에 1칸 점프하는 방식으로 간다면, 위와 같이 3가지 방식이 존재하는 것이다.

4번 5번 방법을 보면 공통점이 있다.
4. 시작점 - 1번칸 - 2번칸 - 4번칸

5. 시작점 - 2번칸 - 4번칸

바로 2번칸을 공통적으로 거쳐서 간다는 것이다. 그리그 그 과정들을 보면,

시작점 - 1번칸 - 2번칸

시작점 - 2번칸

으로 2가지 방식이 있는데, 이 방식들은 모두 우리가 기존에 계산했던 "2번칸 까지 갈 수 있는 방법들"에 속하는 것이다.

즉, 4번칸으로 가기 위해서는, 2번칸으로 간 후에 2칸을 한번에 점프하는 방식으로 간다면, 위와 같이 2가지 방식이 존재하는 것이다.

즉, 우리는 N번칸에 도달하기 위해서는, 크게 2가지 방법으로 나눠볼 수가 있다.

1. N - 2번칸 까지 도달한 후에, 2칸을 점프해서 N번칸에 도착하는 방법

2. N - 1번칸 까지 도달한 후에, 1칸을 점프해서 N번칸에 도착하는 방법

이렇게 2가지 방법이 있다. 그 경우의 수는 당연히 F[N] = F[N - 1] + F[N - 2]가 될 것이다.

[ 소스코드 ]

#include <string>
#include <vector>
 
#define MODULER 1234567
using namespace std;
 
long long solution(int n) 
{
    vector<long long> DP(n + 1, 0);
    DP[1] = 1;
    DP[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        DP[i] = DP[i - 1] + DP[i - 2];
        DP[i] = DP[i] % MODULER;
    }
    return DP[n] % MODULER;
}