백준 24392 영재의 징검다리 C++

푸앙이 게임에 참가한 영재는 유리 징검다리 게임을 통과해야 한다.

유리 징검다리 게임의 규칙은 간단하다. 총 N번의 걸음을 통해 건널 수 있고, 각 걸음마다 M개의 칸이 있다. 영재는 시작점(N - 1 번째 줄)의 한 칸에서 건너기 시작해 이후 앞의 인접한 최대 3개의 유리 중 하나를 선택해 건너갈 수 있다. 밟은 칸이 강화유리라면 안전하게 건널 수 있지만, 일반 유리는 밟을 수 없다.

다음은 N = 3, M = 5인 어느 순간에 영재가 가능한 이동을 나타낸 그림이다.

다리의 정보가 주어지면, 영재가 다리를 무사히 건널 수 있는 경우의 수를 알아내보자.

입력

첫 줄에 N과 M(1 ≤ N, M ≤ 1,000)이 공백으로 구분되어 주어지고, 그 뒤에는 N줄에 걸쳐 다리의 정보가 주어진다.

강화유리의 경우 1, 일반 유리의 경우 0으로 주어진다.

출력

영재가 무사히 다리를 건널 수 있는 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

---

2차원 DP를 이용해 해결하였고, 주의할 점은 int로 선언시 오버플로우가 발생한다는 점입니다.

long long을 선언해서 오버플로우를 막을 수 있었습니다.

먼저 제일 밑부터 위로 이동을 하는데, 1로 적힌 칸만 이동 가능합니다.

만약 테이블의 제일 처음 열이라면 바로 위, 오른쪽만 체크하면 되고,

제일 마지막 열이라면 바로 위, 왼쪽만 체크하고, 그외에는 바로 위,왼쪽,오른쪽 3방향을 체크해서

DP테이블을 갱신하였습니다.

---

전체 소스 코드 ->

#include <iostream>
#define MOD 1000000007 //나머지
using namespace std;
long long dp[1001][1001]; //오버플로우에 주의하자..
int map[1001][1001];
int main(void){

    int n,m;
    cin >> n >> m;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            cin >> map[i][j];
            if(i == n-1 && map[i][j] == 1){ //처음 이동가능한 칸 세팅
                dp[i][j] = 1;
            }
        }
    }

    long long sum = 0;
    for(int i = n-2;i>=0;i--){
        for(int j = 0;j<m;j++){
            if(map[i][j] == 1){ //이동 가능하면
                if(j == 0){ //제일 처음 열인 경우
                    if(map[i+1][j] == 1){
                        dp[i][j] = (dp[i][j] + dp[i+1][j]) % MOD;

                    }
                    if(map[i+1][j+1] == 1){
                        dp[i][j] = (dp[i][j] + dp[i+1][j+1]) % MOD;
                    }
                }
                else if(j == m-1){ //제일 마지막 열인 경우
                    if(map[i+1][j] == 1){
                        dp[i][j] = (dp[i][j] + dp[i+1][j]) % MOD;
                    }
                    if(map[i+1][j-1] == 1){
                        dp[i][j] = (dp[i+1][j-1] + dp[i][j]) % MOD;
                    }
                }
                else{ //그 외의 경우
                    if(map[i+1][j-1] == 1){
                         dp[i][j] = (dp[i][j] + dp[i+1][j-1]) % MOD;
                    }
                    if(map[i+1][j] == 1){
                         dp[i][j] = (dp[i][j] + dp[i+1][j]) % MOD;
                    }
                    if(map[i+1][j+1] == 1){
                         dp[i][j] = (dp[i][j] + dp[i+1][j+1]) % MOD;
                    }
                }

            }

        }

    }

    for(int i = 0;i<m;i++){ //제일 위에서 최종적으로 도착가능한 경우(입력 배열이 1인 경우)
        if(map[0][i] == 1){
            sum += (dp[0][i]);
        }
    }
    cout << sum % MOD;
}