3114번 사과와 바나나

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

dp cache 캐시 동적 계획 다이나믹 복습 필수 코딩 추천 gs18115 누적합 바나나 사과 boj 백준 코테

Slack에서 gs18115님의 도움을 받아 풀 수 있었다.

내가 놓친 부분은 총 2가지 인데,

1. 1행과 1열을 따로 전처리 하는 과정을 포함해야 했었다. 그리고 이중 for문 시작을 i=2,j=2로 시작했어야 했다.

- 나는 전처리 없이 이중 for문에서 i=1, j=1로 시작했었다.

또한, 1행, 1열 전처리 없이 이중 for문에서 i=1, j=1로 시작하면 안 되는 이유는 i=1, j=1로 시작하면, 1행 C열이나 R행 1열로도 시작할 수 있기 때문이다.

gs18115님 답 :

무조건 1행 1열에서 시작해야 하는데, for문을 1행과 1열에서 돌리면 1행 n열 또는 m행 1열에서 시작할 수 있어요

https://acmicpc.slack.com/archives/C081U6CS3/p1585112739018000?thread_ts=1585110948.016100&cid=C081U6CS3

2. 아래로 내려가는 경우 바나나를 포함하면 안 됐었다. 이미 지나간 경로이기 때문이다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 1502
 
/*
cache[i][j] : 불도저가 i행 j열 일 때의 사과와 바나나의 합의 최댓값
*/
 
int cache[Max][Max], R, C, a[Max][Max], b[Max][Max];
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    cin >> R >> C;
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            char c;
            int n;
 
            cin >> c >> n;
 
            if (c == 'A') {
                a[i][j] = n;
            }
            else if (c == 'B') {
                b[i][j] = n;
            }
        }
    }
 
    // 누적합
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            a[i][j] += a[i][j - 1]; // →
            b[i][j] += b[i][j - 1]; // →
        }
    }
 
    // 누적합
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            a[i][j] += a[i - 1][j]; // ↓
            b[i][j] += b[i - 1][j]; // ↓
        }
    }
 
    // 1행
    for (int j = 1; j <= C; j++) {
        cache[1][j] = a[R][j] - a[1][j];
    }
 
    // 1열
    for (int i = 1; i <= R; i++) {
        cache[i][1] = a[R][1] - a[i][1];
    }
 
    for (int i = 2; i <= R; i++) {
        for (int j = 2; j <= C; j++) {
 
            /*
            위 바나나
            아래 사과
            */
 
            // →
            cache[i][j] = max(cache[i][j],
                cache[i][j - 1]
                + b[i - 1][j] - b[i - 1][j - 1] - b[0][j] + b[0][j - 1]
                + a[R][j] - a[R][j - 1] - a[i][j] + a[i][j - 1]);
 
            // ↓
            if (i - 2 >= 0) {
                cache[i][j] = max(cache[i][j],
                    cache[i - 1][j]
                    - (a[i][j] - a[i][j - 1] - a[i - 1][j] + a[i - 1][j - 1]));
            }
 
            // ↘
            cache[i][j] = max(cache[i][j], 
                cache[i - 1][j - 1] 
                + b[i - 1][j] - b[i - 1][j - 1] - b[0][j] + b[0][j - 1]
                + a[R][j] - a[R][j - 1] - a[i][j] + a[i][j - 1]);
        }
    }
 
    printf("%d\n", cache[R][C]);
 
    return 0;
}