백준 5569번 출근 경로[C++]

1. 문제 풀이

 문제 유형은 다이나믹 프로그래밍입니다. dp테이블을 4차원 배열로 정의한 다음 점화식을 세워서 top-down approach로 풀이했습니다. 재귀 호출 형식은 코드 주석으로 써놓았으니 dp 테이블만 이야기하겠습니다.

// d[cx][cy][dir][curvable] : (cx, cy)에서 dir 방향으로 이동중일 때 경우의수
// * curvable = 0 : 현재 회전 불가능
// * curvable = 1 : 현재 회전 가능
int d[105][105][2][2];

 

이런 dfs 형식의 다이나믹 프로그래밍은 개인적으로 top-down approach가 더 쉬운 것 같습니다.

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int MOD = 100'000;
const int dx[2] = { 1, 0 };
const int dy[2] = { 0, 1 };

int n, m;
int d[105][105][2][2];

int solve(int cx, int cy, int dir, int curvable) {
    if(cx == n && cy == m) {
        return 1;
    }

    if(d[cx][cy][dir][curvable] != -1) {
        return d[cx][cy][dir][curvable];
    }

    d[cx][cy][dir][curvable] = 0;

    // 방향을 바꾸지 않는다.  
    int nx = cx + dx[dir];
    int ny = cy + dy[dir];

    // 범위 내일 때.
    if(nx <= n && ny <= m) {
        // curvable이 0이었던 상태인 경우 curvable을 1로 바꾼다.
        d[cx][cy][dir][curvable] = solve(nx, ny, dir, curvable | 1);
    }    

    // curvable이 1이었을 때, 방향을 바꿔본다.
    if(curvable) {
        int nx = cx + dx[!dir];
        int ny = cy + dy[!dir];
        if(nx <= n && ny <= m) {
            d[cx][cy][dir][curvable] += solve(nx, ny, !dir, curvable & 0);
        }
    }

    return d[cx][cy][dir][curvable] %= MOD;
}

int main() {
    fastio(nullptr, false);

    cin >> n >> m;
    memset(d, -1, sizeof(d));

    cout << (solve(1, 2, 1, 1) + solve(2, 1, 0, 1)) % MOD;
}

 

3. 제출 결과