백준 24430, 알고리즘 수업 - 행렬 경로 문제 7

개요

문제 링크
골드 3, DP
최대 이득 경로에 포함되는 특정점의 개수의 최댓값 구하기

---

접근

1. 단순한 2차원 dp, 우선 dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1])을 이해하고 있어야 한다.
   이유는 (현재 최대 이득) = (현재 추가되는 이득) + (과거 최대 이득)
2. 특정점의 수는 어떻게 구하냐, 만약 왼쪽과 위의 이득이 다르면 무조건 큰 쪽의 특정점을 더해준다. 이유는 이득을 최대화하는 것이 특정점의 수를 최대화 하는 것보다 우선되기 때문.
3. 그리고 왼쪽과 위의 이득이 같다면 특정점의 수가 더 큰 쪽을 더해준다.

---

Pseudo code

이득[현재] = max(이득[왼쪽], 이득[위]) + 추가이득[현재]
if (이득[왼쪽] == 이득[위])
    특정점[현재] += max(특정점[왼쪽], 특정점[위])
else if (왼쪽 이득이 더 크면)
    특정점[현재] += 특정점[왼쪽]
else if (위가 더 크면)
    특정점[현재] += 특정점[위]

---

Source code

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int a[N][N];
int m[N][N];
int dp[N][N][2];

int main() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin >> a[i][j];
    int p, x, y;
    cin >> p;
    for (int i=0; i<p; i++) {
        cin >> x >> y;
        m[x][y] = 1;
    }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++) {
            dp[i][j][0] = a[i][j];
            dp[i][j][1] = m[i][j];
            if (dp[i-1][j][0] == dp[i][j-1][0]) {
                dp[i][j][0] += dp[i][j-1][0];
                dp[i][j][1] += max(dp[i][j-1][1], dp[i-1][j][1]);
            } else if (dp[i-1][j][0] < dp[i][j-1][0]) {
                dp[i][j][0] += dp[i][j-1][0];
                dp[i][j][1] += dp[i][j-1][1];
            } else {
                dp[i][j][0] += dp[i-1][j][0];
                dp[i][j][1] += dp[i-1][j][1];
            }
        }
    cout << dp[n][n][0] << " " << dp[n][n][1];
}