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

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

입출력 예

Solution

#include <string>
#include <vector>

using namespace std;

int dp[2001];

long long solution(int n) {
    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= n; i++){
        dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
    }
    return dp[n];
}

사실 진짜 간단한 문제다.

만약 1칸짜리 칸에서 멀리뛰기를 한다면 당연히 아래와 같을 것이다.

(1칸)

2칸짜리 칸에서 멀리뛰기를 한다면 아래와 같다.

(1칸, 1칸)
(2칸)

3칸짜리 칸에서 멀리 뛰기를 한다면 아래와 같다.

(1칸, 1칸, 1칸)
(1칸, 2칸)
(2칸, 1칸)

4칸은 위에서 본 것과 같다.

(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)

2칸 짜리 멀리뛰기는 1칸짜리를 2개 합친것과 같다.
3칸짜리 멀리뛰기는 2칸 + 1칸을 한 것과 같다. 어차피 2칸짜리가 1칸 + 1칸일테니까
4칸 짜리도 마찬가지.
5칸을 한번 볼까?

(1칸, 1칸, 1칸, 1칸, 1칸)
(1칸, 1칸, 1칸, 2칸)
(1칸, 1칸, 2칸, 1칸)
(1칸, 2칸, 1칸, 1칸)
(2칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 2칸)
(2칸, 1칸, 2칸)
(2칸, 2칸, 1칸)

총 8개다. 어렵게 생각 할 것 없이 DP로 풀면 되는 문제였다.