BOJ 23325 | 마법천자문

2021 홍익대학교 프로그래밍 경진대회 F번으로 정석적인 DP 문제다.
요즘 DP를 거의 안해서 DP력이 크게 떨어졌다는 사실이 확 느껴지는 문제였다.

역시 수능 + 겨울방학 조합은 사람을 엄청 무디게 만드는 것 같다.

<수> <연산자> <수> <연산자> 같이 번갈아 나오는 특성을 이용해서 초기값은 수동으로 구하고 나머지는 dp[n]까지 반복문 돌리면 맞을 것 같았다.

다만 <수> 가 +, -, +- 3종류였기 때문에 1글자와 2글자 중 어떤 것일지 모르기 때문에 두 가지 유형으로 나눠서 생각해야 한다.

dp[i]를 구하는 과정이다.
첫 번째 경우는 arr[i-1]이 연산자인 경우다.
이 때는 arr[i]가 <수> , arr[i-1]이 <연산자>, dp[i-2]가 <수> 여야 성립한다.

따라서 이 경우는 dp[i-2]이 존재하는 모든 i에 대해 가능하다.

두 번째 경우는 arr[i-1]가 '+'이고, arr[i]가 '-'여서 '+-'이 통째로 11이라는 <수>로 인식되는 경우이다.

이 때는 arr[i-1]arr[i]이 <수>, arr[i-2]가 <연산자>, dp[i-3]이 <수>여야 성립힌다.

따라서 이 경우는 dp[i-3]이 존재하고, arr[i-1]arr[i] 가 '+-' 일 때 가능하다.

조건을 따져가며 두 가지 경우에 따라 dp[i]를 채우고 혹여나 두 가지 경우 모두 불가능하다면 dp[i]의 값을 INT_MAX로 설정하여 값이 없다는 것을 나타내야 한다.

계산 과정 중에서 dp[i]는 음수일 수 있기 때문에 dp의 초기값 설정은 INT_MIN으로 하였다.

코드

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

#ifdef LOCAL
constexpr bool local = true;
#else
constexpr bool local = false;
#endif

#define debug if constexpr (local) std::cout
#define endl '\n'

int dp[200001];

int main(){
	string arr; cin >> arr;
	
	//exception
	if (arr.length() == 1){
		cout << ((arr[0] == '+') ? 10 : 1);
		return 0;
	}
	else if (arr.length() == 2){
		cout << 11;
		return 0;
	}
	
	dp[0] = (arr[0] == '+') ? 10 : 1;
	if (arr[1] == '+') dp[1] = INT_MAX;
	else{
		if (arr[0] == '+') dp[1] = 11;
		else dp[1] = INT_MAX;
	}
	
	int t = (arr[2] == '+') ? 10 : 1;
	if (arr[1] == '+') dp[2] = dp[0] + t;
	else dp[2] = dp[0] - t;
	
	debug << dp[0] << ' ' << dp[1] << ' ' << dp[2] << ' ';
	
	for (int i = 3; i < arr.length(); i++){
		int flag = 0;
		dp[i] = INT_MIN;
		if (dp[i-2] != INT_MAX){ // dp[i] = arr[i] arr[i-1] dp[i-2]
			flag++;
			t = (arr[i] == '+') ? 10 : 1;
			dp[i] =  (arr[i-1] == '+') ? dp[i-2]+t : dp[i-2]-t;
		}
		
		if (dp[i-3] != INT_MAX && arr[i] == '-' && arr[i-1] == '+'){ // dp[i] = arr[i]arr[i-1] arr[i-2] dp[i-3]
			flag++;
			dp[i] = max(dp[i], (arr[i-2] == '+') ? dp[i-3]+11 : dp[i-3]-11);
		}
		
		if (!flag) dp[i] = INT_MAX;
		
		debug << dp[i] << ' ';
	}
	
	cout << dp[arr.length() - 1];
	
}