17069 c++ - 파이프 옮기기 2

17070번. 파이프 옮기기 1 과 같은 문제이지만 N(3 ≤ N ≤ 32)의 범위가 굉장히 넓기 때문에 dp를 적용해야만 풀 수 있습니다.  + int형을 return값으로 가지게 되면 오버플로우가 나므로 ll을 사용하여 풀어야 합니다.

완전탐색으로 풀었지만, 시간초과가 나게 되어서 dp에 대한 고민을 많이 해볼 수 있는 문제였습니다.

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

#define fastio ios::sync_with_stdio(0), cin.tie(0)

ll n;
ll dx[] = {1, 1, 0};
ll dy[] = {0, 1, 1};

ll dfs(ll y, ll x, ll dir, vector<vector<ll>> &b,
       vector<vector<vector<ll>>> &v) {
  if (y == n - 1 && x == n - 1) {
    return 1;
  }

  if (v[y][x][dir] != -1) {
    return v[y][x][dir];
  }

  v[y][x][dir] = 0;

  for (ll i = 0; i < 3; i++) {
    ll ny = y + dy[i];
    ll nx = x + dx[i];

    if (dir == 0 && i == 2) continue;
    if (dir == 2 && i == 0) continue;

    if (ny < 0 || nx < 0 || ny >= n || nx >= n || b[ny][nx] == 1) continue;
    if (i == 1 && (b[ny - 1][nx] == 1 || b[ny][nx - 1] == 1)) continue;

    v[y][x][dir] += dfs(ny, nx, i, b, v);
  }

  return v[y][x][dir];
}

int main() {
  fastio;

  cin >> n;
  vector<vector<ll>> b(n, vector<ll>(n, 0));

  // 메모이제이션 배열을 3차원으로 선언:
  // [y][x][dir] (dir: 0=가로, 1=대각선, 2=세로)
  vector<vector<vector<ll>>> v(n, vector<vector<ll>>(n, vector<ll>(3, -1)));

  for (ll i = 0; i < n; i++) {
    for (ll j = 0; j < n; j++) {
      cin >> b[i][j];
    }
  }

  if (b[0][1] == 1) {
    cout << "0";
    return 0;
  }

  cout << dfs(0, 1, 0, b, v);

  return 0;
}

오버플로우 에러