경곽이의 칸 점프

### 문제 경곽이는 0번 칸에서 출발해 정확히 $n$번 칸에 도착하려고 한다. 경곽이는 한 번에 $a$칸 또는 $b$칸만 움직일 수 있다. 경곽이가 $n$번 칸에 도달할 수 있는 방법의 수를 구하라. 점프 순서가 다르면 서로 다른 방법으로 친다. 답이 매우 클 수 있으니 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다. ### 상태와 전이로 접근 이 문제는 **상태와 다섯 가지 조건**으로 정리하면 그대로 풀린다. - **상태**: 현재 위치 $x$ (한 정수면 충분하다) - **초기 상태**: $x = 0$ - **목표 상태**: $x = n$ - **실패 조건**: $x > n$ (지나쳐 버렸음) - **제약 조건**: 한 번에 $a$칸 또는 $b$칸만 이동 - **전이**: $x \to x + a$ 또는 $x \to x + b$ 이렇게 정리하면 점화식이 따라 나온다. $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)$. ```c 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$로 초기화해 둬야 한다.