취미로 코딩하기

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

이번에 볼 문제는 백준 24428번 문제인 알고리즘 수업 - 행렬 경로 문제 5이다.
문제는 아래 링크를 확인하자.

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

점수가 최대가 되는 경로를 찾는 일반적인 문제를 풀듯이 문제를 해결할 수 있다.

현재 칸까지 이동하면서 "중간 지점"을 들린 횟수를 0회, 1회, 2회 및 3회 이상으로 구분하여 각 횟수별로 최댓값을 각각 구해가며 문제를 해결하자.

구현시 다양한, 특히 첫 행 및 첫 열과 관련된 코너케이스에 유의하여 구현하자.

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

#include <iostream>
using namespace std;
typedef long long ll;

ll arr[1001][1001];
ll dp[1001][1001][4];
bool chk[1001][1001];

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

	int N; cin >> N;
	for (int i = 2; i <= N; i++) arr[i][0] = arr[0][i] = -1000000007;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> arr[r][c];
		}
	}

	int P; cin >> P;
	while (P--) {
		int r, c; cin >> r >> c;
		chk[r][c] = 1;
	}

	for (int r = 0; r <= N; r++) {
		for (int c = 0; c <= N; c++) {
			if (r) {
				if (c) {
					dp[r][c][0] = arr[r][c] + max(dp[r - 1][c][0], dp[r][c - 1][0]);
					if (max(dp[r - 1][c][1], dp[r][c - 1][1])) dp[r][c][1] = arr[r][c] + max(dp[r - 1][c][1], dp[r][c - 1][1]);
					if (max(dp[r - 1][c][2], dp[r][c - 1][2])) dp[r][c][2] = arr[r][c] + max(dp[r - 1][c][2], dp[r][c - 1][2]);
					if (max(dp[r - 1][c][3], dp[r][c - 1][3])) dp[r][c][3] = arr[r][c] + max(dp[r - 1][c][3], dp[r][c - 1][3]);
					if (chk[r][c]) {
						if (max(dp[r - 1][c][2], dp[r][c - 1][2])) dp[r][c][3] = max(dp[r][c][3], arr[r][c] + max(dp[r - 1][c][2], dp[r][c - 1][2]));
						if (max(dp[r - 1][c][1], dp[r][c - 1][1])) dp[r][c][2] = max(dp[r][c][2], arr[r][c] + max(dp[r - 1][c][1], dp[r][c - 1][1]));
						if (max(dp[r - 1][c][0], dp[r][c - 1][0])) dp[r][c][1] = max(dp[r][c][1], arr[r][c] + max(dp[r - 1][c][0], dp[r][c - 1][0]));
					}
				}
				else {
					dp[r][c][0] = arr[r][c] + dp[r - 1][c][0];
					if (dp[r - 1][c][1]) dp[r][c][1] = arr[r][c] + dp[r - 1][c][1];
					if (dp[r - 1][c][2]) dp[r][c][2] = arr[r][c] + dp[r - 1][c][2];
					if (dp[r - 1][c][3]) dp[r][c][3] = arr[r][c] + dp[r - 1][c][3];
				}
			}
			else {
				if (c) {
					dp[r][c][0] = arr[r][c] + dp[r][c - 1][0];
					if (dp[r][c - 1][1]) dp[r][c][1] = arr[r][c] + dp[r][c - 1][1];
					if (dp[r][c - 1][2]) dp[r][c][2] = arr[r][c] + dp[r][c - 1][2];
					if (dp[r][c - 1][3]) dp[r][c][3] = arr[r][c] + dp[r][c - 1][3];
				}
			}
		}
	}

	if (dp[N][N][3]) cout << dp[N][N][3];
	else cout << -1;
}