경곽이의 칸 점프

문제

경곽이는 0번 칸에서 출발해 정확히 $n$번 칸에 도착하려고 한다. 경곽이는 한 번에 $a$칸 또는 $b$칸만 움직일 수 있다.

경곽이가 $n$번 칸에 가닿는 방법의 수를 구하라. 점프 순서가 다르면 서로 다른 방법으로 친다. 답이 매우 클 수 있으니 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다.

상태와 전이로 접근

이 문제는 상태와 다섯 가지 조건으로 정리하면 그대로 풀린다.

• 상태: 현재 위치 $x$ (한 정수면 충분하다)
• 초기 상태: $x = 0$
• 목표 상태: $x = n$
• 실패 조건: $x > n$ (지나쳐 버렸음)
• 제약 조건: 한 번에 칸 또는 칸만 이동

이렇게 정리하면 점화식이 따라 나온다. $f(x)$를 "$x$번 칸에서 출발해 $n$번 칸에 가닿는 방법의 수"라고 정의하면:

$f(x) = \begin{cases} 1 & x = n \\ 0 & x > n \\ f(x + a) + f(x + b) & \text{그 외} \end{cases}$

답은 $f(0)$이다.

메모이제이션

순수 재귀로 짜면 같은 상태를 수없이 다시 부른다. $n$이 크면 시간 안에 못 끝난다.

각 상태의 결과를 배열에 저장해 두면 한 상태당 한 번씩만 계산한다. 메모이제이션으로 $O(n)$.

long long memo[1000005];
int n, a, b;

long long search(int x) {
  if (x > n) return 0;
  if (x == n) return 1;
  if (memo[x] != -1) return memo[x];
  return memo[x] = (search(x + a) + search(x + b)) % 1000000007;
}

호출 전에 memo 배열을 전부 $-1$로 초기화해 둬야 한다.

제한

• $1 \le n \le 10^6$
• $1 \le a < b \le n$ (반드시 가 보장된다)