boj 3114 사과와 바나나

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

 

(1, 1)에서 출발하여 (N, M)에 도착했을 때 사과 + 바나나의 최대를 구하는 문제입니다.

이동은 아래, 오른쪽, 오른쪽 + 아래 만 가능합니다.

 

(x, y) 기준 사과 + 바나나의 합은

1. (x, y) ~ (x - 1, y) 까지는 바나나

2. (x + 1, y) ~ (N, y) 까지는 사과

두개를 더하여 계산합니다.

그렇다면 사과와 바나나의 누적합은 각각 구할 수 있고, 세로별로 누적합을 구하도록 합니다.

 

세팅이 완료되었다면 점화식을 구해봅니다.

이동 가능한 방향이 어떻게 되는지를 이용하면 (x, y) 기준 3개 중 하나를 답으로 가져갈 수 있습니다.

(x - 1, y - 1), (x, y - 1)에서 왔을 경우 y 좌표가 바꼈으므로 이전에 구했던 누적합을 더하면 됩니다.

(x - 1, y)에서 왔을 경우 y좌표가 바뀌지 않았으므로 누적합 범위를 조정해야 합니다.

 

dp 값을 채워나가는 도중에 dp[N][M]보다 커지는 경우가 있을 수 있으니 dp[N][M]를 명시하여 출력해주시면 되겠습니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 1501
using namespace std;
 
int sumA[MAX][MAX], sumB[MAX][MAX], dp[MAX][MAX];
int N, M;
 
void func() {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (j == 1) {
                dp[i][j] = sumA[N][j] - sumA[i][j];
                continue;
            }
 
            int tmp = sumA[N][j] - sumA[i][j] + sumB[i - 1][j];
            dp[i][j] = max(max(dp[i - 1][j - 1], dp[i][j - 1]) + tmp, dp[i - 1][j] - sumA[i][j] + sumA[i - 1][j]);
        }
    }
 
    cout << dp[N][M] << '\n';
}
 
void input() {
    char ch;
    int x;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            cin >> ch >> x;
            if (ch == 'A') {
                sumA[i][j] = x;
            }
            else {
                sumB[i][j] = x;
            }
            sumA[i][j] += sumA[i - 1][j];
            sumB[i][j] += sumB[i - 1][j];
        }
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}