백준 17070번: 파이프 옮기기 1 (C++)

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

삼성 상시 검정 A형 기출 문제이다. 삼성의 문제이니만큼 완전탐색 혹은 시뮬레이션 문제일 것이다.

하지만 이를 생각하더라도, 동적계획법을 통해서 너무 쉬운 풀이가 가능하기 때문에 DP를 활용해서 간단하게 풀었다.

정점 i,j에 도착할 때, 어떤 방향 상태를 가지고 도착하는지 생각해보면, 세가지가 가능함을 알 수 있다.

//1-indexed
#include<iostream>
 
using namespace std;
int m[18][18], d[18][18][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;
}