3회 문제풀이 08 / ABC 129 C - Typical Stairs
ABC 129 C - Typical Stairs
【문제 개요】
N단의 계단이 있습니다. 타카하시군은 현재 0단에 있습니다. 타카하시군은 한 걸음으로 1단이나 2단을 올라갈 수 있습니다.
단, a1, a2, a3, …, aM단의 계단은 깨져있어서 그 단을 밟는것은 위험합니다.
깨진 바닥을 밟지 않도록 하면서 최상단(N단)에 도착하기 까지의 이동 방법은 총 몇가지 있습니까?
총 수를 1,000,000,007로 나눈 값의 나머지를 구하시오.
【전제】
- 1 ≦ N ≦ 10^5
- 0 ≦ M ≦ N-1
- 1 ≦ a1 < a2 < … < aM ≦ N-1
【입력 형태】
1
2
3
4
5
N M
a1
a2
...
aM
【출력 형태】
조건을 만족시키는 이동 방법의 총 수를 1,000,000,007로 나눈 나머지를 출력하시오.
【예시】
입력 예 1
1
2
6 1
3
출력 예 1
1
4
이동 방법은 다음과 같이 4가지입니다.
- 0 → 1 → 2 → 4 → 5 → 6
- 0 → 1 → 2 → 4 → 6
- 0 → 2 → 4 → 5 → 6
- 0 → 2 → 4 → 6
입력 예 2
1
2
3
10 2
4
5
출력 예 2
1
0
깨진 바닥을 밟지 않고 이동하는 방법은 없습니다.
입력 예 3
1
2
3
4
5
6
100 5
1
23
45
67
89
출력 예 3
1
608200469
총 수 1,000,000,007로 나눈 나머지를 출력하는것에 주의해주세요.
ABC 129 C - Typical Stairs
【문제 개요】
N단의 계단이 있습니다. 타카하시군은 현재 0단에 있습니다. 타카하시군은 한 걸음으로 1단이나 2단을 올라갈 수 있습니다.
단, a1, a2, a3, …, aM단의 계단은 깨져있어서 그 단을 밟는것은 위험합니다.
깨진 바닥을 밟지 않도록 하면서 최상단(N단)에 도착하기 까지의 이동 방법은 총 몇가지 있습니까?
총 수를 1,000,000,007로 나눈 값의 나머지를 구하시오.
【전제】
- 1 ≦ N ≦ 10^5
- 0 ≦ M ≦ N-1
- 1 ≦ a1 < a2 < … < aM ≦ N-1
【입력 형태】
1
2
3
4
5
N M
a1
a2
...
aM
【출력 형태】
조건을 만족시키는 이동 방법의 총 수를 1,000,000,007로 나눈 나머지를 출력하시오.
【예시】
입력 예 1
1
2
6 1
3
출력 예 1
1
4
이동 방법은 다음과 같이 4가지입니다.
- 0 → 1 → 2 → 4 → 5 → 6
- 0 → 1 → 2 → 4 → 6
- 0 → 2 → 4 → 5 → 6
- 0 → 2 → 4 → 6
입력 예 2
1
2
3
10 2
4
5
출력 예 2
1
0
깨진 바닥을 밟지 않고 이동하는 방법은 없습니다.
입력 예 3
1
2
3
4
5
6
100 5
1
23
45
67
89
출력 예 3
1
608200469
총 수 1,000,000,007로 나눈 나머지를 출력하는것에 주의해주세요.