시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.5 초 | 512 MB | 1099 | 414 | 305 | 36.310% |
푸앙이 게임에 참가한 영재는 유리 징검다리 게임을 통과해야 한다.
유리 징검다리 게임의 규칙은 간단하다. 총 N번의 걸음을 통해 건널 수 있고, 각 걸음마다 M개의 칸이 있다. 영재는 시작점(N - 1 번째 줄)의 한 칸에서 건너기 시작해 이후 앞의 인접한 최대 3개의 유리 중 하나를 선택해 건너갈 수 있다. 밟은 칸이 강화유리라면 안전하게 건널 수 있지만, 일반 유리는 밟을 수 없다.
다음은 N = 3, M = 5인 어느 순간에 영재가 가능한 이동을 나타낸 그림이다.
다리의 정보가 주어지면, 영재가 다리를 무사히 건널 수 있는 경우의 수를 알아내보자.
첫 줄에 N과 M(1 ≤ N, M ≤ 1,000)이 공백으로 구분되어 주어지고, 그 뒤에는 N줄에 걸쳐 다리의 정보가 주어진다.
강화유리의 경우 1
, 일반 유리의 경우 0
으로 주어진다.
영재가 무사히 다리를 건널 수 있는 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.
3 2 0 1 1 0 0 1
1
5 5 1 0 1 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1
9
4 4 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1
8
University > 중앙대학교 > 2022 중앙대학교 CHAC (ChAOS Hello2022 Algorithm Contest) C번