백준 3114 사과와 바나나 (C++)

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

3114번: 사과와 바나나

누적합과 dp를 사용하는 문제였습니다. 시간복잡도가 엄청 빡빡하지 않아서 좀 안좋게 짠거같은데도 ac받아서 다행입니다. 

먼저 경계선은 각 열마다 어떤 행을 고르는 걸로 생각할 수 있습니다. 열마다 선택한 행 아래 A개수 위의 B개수를 생각하면 됩니다. 각 열마다 열의 A개수와 B개수는 독립적이니까요. 말을 어렵고 이상하게 했는데 경계선을 예시로 그려보시면 어떤 얘기인지 알것 같습니다.

움직일 수 있는 방향은 오른쪽 오른쪽아래대각선 아래이므로 이에대해 dp를 구해주면 됩니다. 0열과 M열이 특이 케이스인데 0열은 B를 얻어갈수없고 M열은 A를 얻어갈수없으므로 이에대한 처리만 해주시면 되겠습니다.

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<bitset>
#include<string>
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int N,M;
int arr[1502][1502][2];
int arr2[1502][1502][2];
int dp[1502][1502];
int main(){
    fast_io();
    cin>>N>>M;
    for(int x=1;x<=N;x++){
        for(int y=1;y<=M;y++){
            string input;
            cin>>input;
            arr[x][y][input[0]-'A']=stoi(input.substr(1));
        }
    }
    for(int x=1;x<=M;x++){
        int temp=arr[0][x][1];
        for(int y=1;y<=N;y++){
            arr2[y][x][1]=arr[y][x][1];
            if(x==1){
                arr[y][x][1]=0;
                continue;
            }
            int temp2=temp;
            temp+=arr[y][x][1];
            arr[y][x][1]=temp2;
        }
        temp=arr[N+1][x][0];
        for(int y=N;y>=0;y--){
            arr2[y][x][0]=arr[y][x][0];
            if(x==M) {
                arr[y][x][0]=0;
                continue;
            }
            int temp2=temp;
            temp+=arr[y][x][0];
            arr[y][x][0]=temp2;
        }
    }
    for(int x=1;x<=N;x++){
        for(int y=1;y<=M;y++){
            dp[x][y]=max(dp[x][y],dp[x-1][y-1]+arr[x][y][0]+arr[x][y][1]);
            dp[x][y]=max(dp[x][y],dp[x][y-1]+arr[x][y][0]+arr[x][y][1]);
            if(y!=M) dp[x][y]=max(dp[x][y],dp[x-1][y]-arr2[x][y][0]);
            else dp[x][y]=max(dp[x][y],dp[x-1][y]);
        }
    }
    cout<<dp[N][M];
}