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

May 18, 2022

1. 문제

백준 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를 받았다.