[프로그래머스] 멀리 뛰기

점프를 한 칸 또는 두 칸 뛸 수 있을 때, n에 도달할 때까지 나올 수 있는 모든 경우의 수를 구하는 문제.

메모이제이션으로 간단하게 해결 가능하다. foo(i)는 i에서 n까지 가면서 나타날 수 있는 모든 경우의 수를 반환한다.

경우의 수가 int의 범위를 초과할 수 있으나, 문제는 결과를 1234567로 나눈 나머지 값을 요구하므로 모듈러 연산의 덧셈 성질을 이용하여 해결한다.

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

cpp code

using namespace std;

using lld = long long int;

#define M 1234567;

int N;
int memo[2000];

int foo(int i) {
    if (i == N) return 1;
    if (i > N) return 0;
    
    int& ret = memo[i];
    if (ret) return ret;
    
    ret = (ret + foo(i + 1)) % M;
    ret = (ret + foo(i + 2)) % M;
    
    return ret;
}

lld solution(int n) {
    N = n;
    return foo(0);
}