백준 23325 마법천자문 (C++)

 

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

23325번: 마법천자문

dp의 정석적인 문제였습니다. '+' '-' '+-'인 경우가 수가 되고 '+' '-'는 연산자가 될 수 있습니다. 

현재 문자를 input[x]라 하면 input[x]와 input[x-1]은 '-' 아니면 '+'이므로 input[x]는 수가 될수있고 input[x-1]은 연산자가 될 수 있습니다

따라서 (x-2까지의 연산결과 최대값(수)) input[x-1](연산자) input[x](수) 인 경우와

(x-3까지의 연산결과 최대값(수)) input[x-2](연산자) (input[x-1]=='+' && input[x]=='-')11인 경우로 나눠져있습니다. 이를 dp에 적용하면 됩니다.

#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);
}
long long dp[200001];
int main(){
    string input;
    cin>>input;
    int N=(int)input.size();
    for(int x=1;x<N;x++) dp[x]=-2e9;
    dp[0]= input[0]=='+' ? 10 : 1;
    dp[1]=input[0]=='+' && input[1]=='-' ? 11: dp[1];
    for(int x=2;x<N;x++){
        int now= (input[x]=='+') ? 10 : 1;
        if(input[x-1]=='+') dp[x]=dp[x-2]+now;
        else dp[x]=max(dp[x-2]-now,dp[x]);
        if(now==1 && input[x-1]=='+' && x>2){
            if(input[x-2]=='+') dp[x]=max(dp[x],dp[x-3]+11);
            else dp[x]=max(dp[x-3]-11,dp[x]);
        }
    }
    cout<<dp[N-1];
}