백준 17069번: 파이프 옮기기 2 (C++)

https://www.acmicpc.net/problem/17069

간단한 DP 문제이다.

//1-indexed
#include<iostream>
 
using namespace std;
typedef long long ll;
ll m[33][33], d[33][33][3];
int main(void) {
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> m[i][j];
 
    d[1][2][0] = 1; //초기에는 1,2로 가로로 들어가는 방법 한가지
    d[1][2][1] = 0;
    d[1][2][2] = 0;
 
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j <= 2) continue;
            if (m[i][j] == 1)  //현재 지점이 벽이면, 그 지점까지 오는 경로는 모두0 (그냥 스킵해도 초기화 0으로 되어있음)
                continue;
            
            if (m[i][j - 1] == 1) d[i][j][0] = 0; //가로로 들어오는 방법이 없는 경우 = 그 바로 왼쪽 벽인 경우
            else
                d[i][j][0] = d[i][j - 1][0] + d[i][j - 1][2];
 
            if (m[i - 1][j] == 1) d[i][j][1] = 0; //세로로 들어오는 방법이 없는 경우 = 그 바로 위쪽이 벽인 경우
            else
                d[i][j][1] = d[i - 1][j][1] + d[i - 1][j][2];
 
            if (m[i - 1][j] == 1 || m[i][j - 1] == 1) d[i][j][2] = 0; //대각으로 오는 방법이 없는 경우 = 날개 둘 중 하나라도 벽인 경우
            else
                d[i][j][2] = d[i - 1][j - 1][0] + d[i - 1][j - 1][1] + d[i - 1][j - 1][2];
        }
    }
 
    cout << d[n][n][0] + d[n][n][1] + d[n][n][2]; //모든 방향으로 들어오는 경우의 합
 
    return 0;
}