취미로 코딩하기

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

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

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

중간 원소를 거쳐서 가는 경로의 점수의 최댓값은 경로를 출발점에서부터 중간 원소까지, 중간 원소부터 도착점까지의 둘로 나누어 생각하는 것으로 구할 수 있다. 구체적으로, 출발점에서부터 중간 원소까지의 경로의 점수의 최댓값과 중간원소부터 도착점까지의 경로의 점수의 최댓값을 이용하면 중간 원소를 거쳐서 가는 경로의 점수의 최댓값을 계산할 수 있다.

중간 원소를 거치지 않고 가는 경로의 최댓값은 해당 중간원소의 점수를 (사실상의) 음의 무한대로 잡고 계산하는 것으로 간단히 구할 수 있다.

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

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

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

int N, R, C;
ll arr[1001][1001];
ll dp[1001][1001][3];

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

	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];
		}
	}

	cin >> R >> C;
	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 (r == R && c == C) {
						dp[r][c][1] = arr[r][c] + max(dp[r - 1][c][0], dp[r][c - 1][0]);
						dp[r][c][2] = -1000000007;
					}
					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]);
						dp[r][c][2] = arr[r][c] + max(dp[r - 1][c][2], dp[r][c - 1][2]);
					}
				}
				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];
					dp[r][c][2] = arr[r][c] + dp[r - 1][c][2];
				}
			}
			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];
					dp[r][c][2] = arr[r][c] + dp[r][c - 1][2];
				}
				else {
					dp[r][c][0] = dp[r][c][1] = dp[r][c][2] = 0;
				}
			}
		}
	}

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