불러오는 중
이 문제는 상태와 다섯 가지 조건으로 정리하면 그대로 풀린다.
이렇게 정리하면 점화식이 따라 나온다. 를 "번 칸에서 출발해 번 칸에 가닿는 방법의 수"라고 정의하면:
답은 이다.
순수 재귀로 짜면 같은 상태를 수없이 다시 부른다. 이 크면 시간 안에 못 끝난다.
각 상태의 결과를 배열에 저장해 두면 한 상태당 한 번씩만 계산한다. 메모이제이션으로 .
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
4 1 3
출력 1
3
설명: 본문의 예제와 같다. , , 세 가지.
입력 2
7 2 3
출력 2
3
설명: ( - 잠깐, 이니 맞다), (), (). 세 가지.
입력 3
5 2 3
출력 3
2
설명: (), (). 두 가지.
입력 4
6 2 5
출력 4
1
설명: 한 가지뿐 (). 5를 한 번 쓰면 또는 이라 6에 닿을 수 없다.
% 1000000007을 잊지 말자.