[프로그래머스]연습문제 : 멀리 뛰기 (level 3)(c++)

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

코딩테스트 연습 - 멀리 뛰기

 

DP

#include <string>
#include <vector>

using namespace std;

long long solution(int n) {

    const long long MOD = 1234567;

    // cnts[i] : i번째 칸에 도달하는 방법의 수
    vector<long long> cnts(n + 1);
    cnts[0] = cnts[1] = 1;

    /*
        i번째 칸까지 오는 방법 
        = (i - 1번째 칸에서 1 더하기) + (i - 2번째 칸에서 2 더하기)

        점화식
        : cnts[i] = cnts[i - 1] + cnts[i - 2];
    */
    for (int i = 2; i <= n; ++i)
    {
        cnts[i] = (cnts[i - 1] + cnts[i - 2]) % MOD;
    }

    return cnts[n];
}

 

이 문제를 심화시키면 거스름돈 문제가 되는 것 같다. 

 

 

효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다.

멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내,
여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요.

기초적인 DP문제이다.

효진이는 고맙게도(?) 2가지 종류의 점프밖에 하지 못한다.

 

따라서 n번째 칸에 도착하기 위해서는

n - 1번째 칸에서 1칸 점프하는 방법과 n - 2번째 칸에서 2칸 점프하는 방법을 더하면 된다.