[BOJ 23325 // C++] 마법천자문

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 23325번 문제인 마법천자문이다.
문제는 아래 링크를 확인하자.

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

23325번: 마법천자문

문제에서 주어진 식의 형태에 의하면 모든 다항식은 <수>로 끝나야 한다. 따라서 어떤 고정된 인덱스로 끝나는 식의 값의 최댓값의 후보는 (i) 뒤의 두 자리를 제외한 식의 결과의 최댓값에 뒤의 두 자리의 연산을 한 값 또는 (ii) 뒤의 두 자리가 11을 의미할 수 있는 경우 뒤의 세 자리를 제외한 식의 결과의 최댓값에 뒤의 세 자리의 연산을 한 값, 둘로 좁혀진다.

 

단, 식의 길이가 두 자리(혹은 세 자리) 이상인지 여부와, 해당 인덱스까지의 부분문자열이 올바른 식이 될 수 있는지의 여부(------++++++의 경우 올바른 식이 절대 될 수 없다)를 고민해 잘 구현하자. 이는 주어진 식이 올바르게 해석할 수 있다는 조건 하에 적절한 초깃값을 설정해주는 것으로 간단히 처리할 수 있다.

 

초깃값을 잘 설정하여 DP로 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#define INF 1000000007
#include <iostream>
#include <string>
using namespace std;

int chartoint[128];

string s; int slen;
int num[200000];

int oprfunc(int x, int y, char opr) {
	if (opr == '+') return x + y;
	else return x - y;
}
int chrfunc(char c) {
	if (c == '+') return 10;
	else return 1;
}

void solve() {
	num[0] = (s[0] == '+') ? 10 : 1;
	num[1] = (s.substr(0, 2) == "+-") ? 11 : -INF;
	for (int i = 2; i < slen; i++) {
		num[i] = oprfunc(num[i - 2], chrfunc(s[i]), s[i - 1]);
		if (i > 2 && s.substr(i - 1, 2) == "+-") num[i] = max(num[i], oprfunc(num[i - 3], 11, s[i - 2]));
	}

	cout << num[slen - 1];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s; slen = s.length();

	if (slen == 1) {
		if (s[0] == '+') cout << 10;
		else cout << 1;
	}
	else if (slen == 2) cout << 11;
	else solve();
}