[BOJ 25170] 백준 25170번 - 명랑한 아리의 외출

May 18, 2022

1. 문제Permalink

백준 25170번 - 명랑한 아리의 외출 (https://www.acmicpc.net/problem/25170)

현재 상황의 최댓값이 이전 여러 상황들의 최댓값에 의해 결정되므로, dynamic programming을 생각할 수 있다. 또한, $y$ 와 $x$ 가 증가하는 방향으로만 행동하기 때문에, for문으로 처리가 가능하다.

다음과 같이 dp를 정의한다.

$dp[i][j][k]$ $\rightarrow$ $(i, j)$ 에서 $k$ 만큼 시간이 흘렀을 때, 일을 수행한 총 시간의 최댓값

현재 상황이 dp[i][j][k]일 때, 이 값은 다음과 같은 여섯 가지 이전 상황에 의해 만들어진다.

지도의 $(i,\;j)$ 좌표에서의 일들의 개수를 w[i][j], 일들의 총 걸리는 시간을 t[i][j]로 놓으면,

dp[i][j-1][k-1] $\rightarrow$ $(i,\;j-1)에서$ (i,\;j)$로 이동한 경우
dp[i-1][j][k-1] $\rightarrow$ $(i-1,\;j)에서$ (i,\;j)$로 이동한 경우
dp[i-1][j-1][k-1] $\rightarrow$ $(i-1,\;j-1)에서$ (i,\;j)$로 이동한 경우
dp[i][j-1][k-1-t[i][j]] $\rightarrow$ $(i,\;j-1)에서$ (i,\;j) $로 이동하고,$ (i,\;j)$에서 w[i][j]만큼 일을 수행한 경우
dp[i-1][j][k-1-t[i][j]] $\rightarrow$ $(i-1,\;j)에서$ (i,\;j) $로 이동하고,$ (i,\;j)$에서 w[i][j]만큼 일을 수행한 경우
dp[i-1][j-1][k-1-t[i][j]] $\rightarrow$ $(i-1,\;j-1)에서$ (i,\;j) $로 이동하고,$ (i,\;j)$에서 w[i][j]만큼 일을 수행한 경우

다음 여섯 가지 값의 maximum 값으로 dp[i][j][k] 값을 구할 수 있다. 단, k-1-t[i][j]가 $0$ 이상인지 확인해야 하고, dp[?][?][?] 값이 초기화된 적 있는지도 확인해주어야 한다.

boj-25170

dp[?][?][?] 값이 초기화된 적 있는지를 확인하지 않아 WA를 받았다.

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

	#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
	#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
	#define ll long long int
	#define pii pair<int, int>
	#define PQ priority_queue
	#define LEN(v) int(v.size())
	#define ALL(v) v.begin(),v.end()
	#define INF 2e9
	#define LINF 1e18

	int main() {
	FASTIO;
	int N, M, T;
	cin >> N >> M >> T;
	vector<vector<pii>> Map(N + 1, vector<pii>(M + 1));
	vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(M + 1, vector<int>(T + 1, -1)));
	FOR(i, 1, N) {
	FOR(j, 1, M) {
	cin >> Map[i][j].first;
	}
	}
	FOR(i, 1, N) {
	FOR(j, 1, M) {
	cin >> Map[i][j].second;
	}
	}

	dp[1][1][0] = 0;
	FOR(i, 1, N) {
	FOR(j, 1, M) {
	if (i == 1 && j == 1) continue;
	FOR(t, 1, T) {
	int a = dp[i][j - 1][t - 1];
	int b = dp[i - 1][j][t - 1];
	int c = dp[i - 1][j - 1][t - 1];
	int tmp = t - 1 - Map[i][j].second;
	int d = (tmp >= 0 && dp[i][j - 1][tmp] != -1 ? dp[i][j - 1][tmp] + Map[i][j].first : -1);
	int e = (tmp >= 0 && dp[i - 1][j][tmp] != -1 ? dp[i - 1][j][tmp] + Map[i][j].first : -1);
	int f = (tmp >= 0 && dp[i - 1][j - 1][tmp] != -1 ? dp[i - 1][j - 1][tmp] + Map[i][j].first : -1);
	dp[i][j][t] = max({ a, b, c, d, e, f });
	}
	}
	}

	int maxi = 0;
	FOR(t, 0, T) {
	maxi = max(maxi, dp[N][M][t]);
	}
	cout << maxi;

	return 0;
	}