백준 17070 파이프옮기기 1,2 c++ // 재귀dp

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

1. 의사코드

1. dfs("끝" 좌표, 상태 :가로 세로 대각) 의 상태 기록이 필요함

2. 기저사례 : 범위밖, 벽이있음 -> 해당 경우의수는 "0" 개로 처리 -> 배제시키기

3. 좌표가 n-1인경우 -> 정답 -> 1개의 정답으로 처리.

4. 논리부분 : 케이스에 맞게 [초기화, 논리, 리턴] 해주면 끝.

 

2. 시행착오

1. 상태가 대각(2)일때 y-1, x-1도 벽인지 체크해줘야함

2. dfs 호출부에서 (0,0,0)이 아닌 (0,1,0) 으로 호출해야함 // 끝좌표가 (0, 1) 이므로.

 

3. 전체코드

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

typedef long long ll;

ll n, a[33][33], dp[33][33][3];

//우측좌표, 상태 0 1 2(가로 세로 대각) : 그 좌표로오는 경우의수
ll dfs(int y, int x, int state) {
    if (y < 0 || x < 0 || y >= n || x >= n) return 0;
    if (a[y][x] == 1) return 0;
    if (state == 2) {
        if (a[y - 1][x] == 1) return 0;
        if (a[y][x - 1] == 1) return 0;
    }

    if (y == n - 1 && x == n - 1) return 1;
    if (dp[y][x][state] != -1) return dp[y][x][state];

    dp[y][x][state] = 0;
    if (state == 0) {
        dp[y][x][state] += dfs(y, x + 1, 0);
        dp[y][x][state] += dfs(y + 1, x + 1, 2);
    }
    else if (state == 1) {
        dp[y][x][state] += dfs(y + 1, x, 1);
        dp[y][x][state] += dfs(y + 1, x + 1, 2);
    }
    else if (state == 2) {
        dp[y][x][state] += dfs(y, x + 1, 0);
        dp[y][x][state] += dfs(y + 1, x, 1);
        dp[y][x][state] += dfs(y + 1, x + 1, 2);
    }
    return dp[y][x][state];
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;

    memset(dp, -1, sizeof(dp));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> a[i][j];
        }
    }
    cout << dfs(0, 1, 0);
    return 0;
}