백준 24392, 영재의 징검다리

개요

문제 링크
실버 1, DP

세 방향 이동이 가능할 때 경로의 수 구하기

---

접근

1. 단순 2차원 DP.
2. dp[i][j]의 경로는 왼쪽 아래에서 온 것, 아래에서 온 것, 오른쪽 아래에서 온 것의 합
3. 1e9+7 나머지 구할 때 세 수의 합이므로 integer overflow 조심
   ex) 1e9+1e9+1e9 = 3e9 > 2^32

---

Pseudo code

left_down = dp[i-1][j-1];
mid_down = dp[i-1][j];
right_down = dp[i-1][j+1];
dp[i][j] = left_down + mid_down + right_down;

---

Source code

#include <bits/stdc++.h>
using namespace std;

const int R = 1e9+7;
int main() {
    int n, m;
    cin >> n >> m;
    long long dp[n+2][m+2];
    for (int i=0; i<=n+1; i++)
        for (int j=0; j<=m+1; j++)
            dp[i][j] = 0;
    for (int i=n; i>=1; i--)
        for (int j=1; j<=m; j++)
            cin >> dp[i][j];
    for (int i=2; i<=n; i++)
        for (int j=1; j<=m; j++){
            if (dp[i][j])
                dp[i][j] = dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1];
            dp[i][j] %= R;
        }
    long long ans = 0;
    for (int j=1; j<=m; j++) {
        ans += dp[n][j];
        ans %= R;
    }
    cout << ans;
}