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

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

 

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

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

24429번: 알고리즘 수업 - 행렬 경로 문제 6

이 문제에서는 주어지는 모든 칸을 들리는 경로 중 점수가 가장 높은 경로의 점수를 찾아야한다.

 

움직일 수 있는 방향이 오른쪽과 아래쪽 인접한 칸 한 칸씩뿐이므로, 주어지는 칸을 모두 들릴 수 있는지를 먼저 체크하자.

 

주어지는 칸을 모두 들려야한다면 해당하는 칸들을 적절히 정렬하여 각 칸들을 연결하는 사이 구간의 경로의 점수의 최댓값을 구해 문제를 해결하자.

 

구현시 각 칸들을 연결할 때의 첫 행 및 첫 열과 관련된 코너케이스에 유의하여 구현하자.

 

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

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

ll arr[1001][1001];
ll dp[1001][1001];

vector<pair<int, int>> vec;

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

	int N; cin >> N;
	for (int r = 1; r <= N; r++) {
		for (int c = 1; c <= N; c++) {
			cin >> arr[r][c];
		}
	}

	int P; cin >> P;
	for (int i = 0; i < P; i++) {
		int r, c; cin >> r >> c;
		vec.emplace_back(make_pair(r, c));
	}
	vec.emplace_back(make_pair(N, N));
	sort(vec.begin(), vec.end());

	for (int i = 0; i < P - 1; i++) {
		if (vec[i].second > vec[i + 1].second) {
			cout << -1;
			return 0;
		}
	}

	int R = 1, C = 1;
	dp[1][1] = arr[1][1];
	for (auto p : vec) {
		int RR = p.first, CC = p.second;
		for (int r = R; r <= RR; r++) {
			for (int c = C; c <= CC; c++) {
				if (r > R && c > C) dp[r][c] = arr[r][c] + max(dp[r - 1][c], dp[r][c - 1]);
				else if (r > R) {
					if (dp[r - 1][c]) dp[r][c] = arr[r][c] + dp[r - 1][c];
				}
				else if (c > C) {
					if (dp[r][c - 1]) dp[r][c] = arr[r][c] + dp[r][c - 1];
				}
			}
		}
		R = RR, C = CC;
	}

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