프로그래머스 - 멀리뛰기 - C++

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

문제 설명

• 멀리뛰기를 하는데 한번에 갈 수 있는 칸이 1칸 or 2칸 일 때 가야하는 칸 n이 주어지면 갈 수 있는 방법을 1234567로 나눈 나머지를 return 하는 문제이다.

접근 방법

• 전형적인 dp 문제이다. 또 1234567로 나눈 나머지를 return 하라는 것으로 봐서 dp 문제가 확실하다.

• 점화식을 세우는데 1칸과 2칸을 갈 수 있는 것으로 봐서 k는 k-1과 k-2의 식으로 나타내어진다.

• k-2에서 2칸을 가는데 2칸을 갈 수 있는 방번은 1칸-1칸, 2칸이 있다.

• k-1에서 1칸을 가는데 방법은 1칸 한가지 밖에 없다.

• 그런데 k-2에서 1칸-1칸을 가는것이 k-1에서 1칸을 가는것과 방법이 겹친다.

• 따라서 dp[k] = dp[k-1] + 2*dp[k-2] - dp[k-2] = dp[k] = dp[k-1] + dp[k-2] 라는 간단한 점화식이 나온다.

• 1234567로 나눈 나머지만 조심해서 코딩하면 어렵지 않다.

코드

#include <string>
#include <vector>

using namespace std;
long long dp [2001];
long long f(int n){
    if(dp[n]!=0){
        return dp[n];
    }
    dp[n] = (f(n-1)+f(n-2))%1234567;
    return dp[n];
}
long long solution(int n) {
    long long answer = 0;
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    answer = f(n);
    return answer;
}

결과

느낀점

• dp문제는 점화식이 전부다. 아 그리고, 1234567로 나누는거 꼭!! 안하면 오답이더라...