[BOJ 24427 // C++] 알고리즘 수업 - 행렬 경로 문제 4

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

 

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

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

24427번: 알고리즘 수업 - 행렬 경로 문제 4

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

현재 칸까지 이동하면서 "중간 지점"을 들린 경우의 최댓값과 그렇지 않은 최댓값을 둘 다 구해가며 문제를 해결하자.

 

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

 

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

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

ll arr[1001][1001];
ll dp[1001][1001][2];
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 (chk[r][c]) dp[r][c][1] = dp[r][c][0];
					else 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]);
				}
				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];
				}
			}
			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];
				}
			}
		}
	}

	cout << dp[N][N][1];
}