[BOJ 25170 // C++] 명랑한 아리의 외출

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25170번 문제인 명랑한 아리의 외출이다.
문제는 아래 링크를 확인하자.

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

25170번: 명랑한 아리의 외출

dp[r][c][t]를 "시간 t에 r행 c열의 칸까지 막 도착했을 때 이미 마친 일의 수"라고 정의하자.

 

왼쪽 칸에서 이 칸으로 오는 경우, 그냥 온다면 dp[r][c-1][t-1]을 참조해 현재 칸에 시간 t에 오는 경우를 체크할 수 있고 왼쪽 칸에서 일을 하고 오는 경우 dp[r][c-1][t-(일하는 데에 드는 시간)-1]과 왼쪽 칸에서 하게 되는 일의 개수를 참조해 현재 칸에 시간 t에 오는 경우를 체크할 수 있다. 위쪽 칸과 왼쪽위 칸도 같은 방식으로 값을 접근해 체크할 수 있다.

 

위의 과정을 dp를 이용해 구현하는 것으로 문제를 해결하자.

 

각 칸에 도달하는 것이 불가능할 수 있으니 실제로 각 칸이 도달되었는지는 꼭 체크하고 계산하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int R, C, T;
int works[50][50];
int times[50][50];
int dp[50][50][501];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> R >> C >> T;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> works[r][c];
		}
	}
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> times[r][c];
		}
	}
	
	dp[0][0][0] = 1;
	for (int r = 0; r < R;  r++) {
		for (int c = 0; c < C; c++) {
			for (int t = 1; t <= T; t++) {
				int& cur = dp[r][c][t];
				if (r > 0) {
					if (dp[r - 1][c][t - 1]) cur = max(cur, dp[r - 1][c][t - 1]);
					if (t >= (times[r - 1][c] + 1)) {
						if (dp[r - 1][c][t - (times[r - 1][c] + 1)]) cur = max(cur, dp[r - 1][c][t - (times[r - 1][c] + 1)] + works[r - 1][c]);
					}
				}
				if (c > 0) {
					if (dp[r][c - 1][t - 1]) cur = max(cur, dp[r][c - 1][t - 1]);
					if (t >= (times[r][c - 1] + 1)) {
						if (dp[r][c - 1][t - (times[r][c - 1] + 1)]) cur = max(cur, dp[r][c - 1][t - (times[r][c - 1] + 1)] + works[r][c - 1]);
					}
				}
				if (r > 0 && c > 0) {
					if (dp[r - 1][c - 1][t - 1]) cur = max(cur, dp[r - 1][c - 1][t - 1]);
					if (t >= (times[r - 1][c - 1] + 1)) {
						if (dp[r - 1][c - 1][t - (times[r - 1][c - 1] + 1)]) cur = max(cur, dp[r - 1][c - 1][t - (times[r - 1][c - 1] + 1)] + works[r - 1][c - 1]);
					}
				}
			}
		}
	}

	int ans = 0;
	for (int t = 0; t <= T; t++) ans = max(ans, dp[R - 1][C - 1][t]);

	cout << ans - 1;
}