[C++] 백준 1541. 잃어버린 괄호

🌽 문제

🥕 입출력

🥔 풀이

이전글에 find()와 substr() 조합으로 split() 함수를 구현하는 방법을 정리해뒀으니 참고해봐도 좋겠다.

더하기와 빼기만 존재하는 식에 괄호를 추가하여 최솟값을 만드는 문제이다.
괄호는 식을 묶는 애다.
따라서 계산한 값을 최소로 만들려면
더하기들을 최대로 묶어서 계산하고 그 값을 음수로 만들어버리면 된다.

즉, 빼기가 나오는 구간을 기준으로 식을 쪼개고 각각을 계산한 뒤
첫 빼기가 나오기 전 구간의 계산값에서 이전에 계산된 값들을 모두 빼면 된다.

그러면
1. 빼기를 기준으로 입력값 쪼개기
2. 쪼갠 값들을 더하기를 기준으로 다시 쪼개어 식 계산하기
3. 빼기를 기준으로 쪼개진 각각 계산된 값들을, 첫번째 계산값에서 모두 빼기
로 정리할 수 있다.

🥬 코드

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
	string str;
	cin >> str;
	
	vector<string> v;

	int prev = 0;
	int curr = str.find('-');
	while (curr != string::npos) {
		string tmp = str.substr(prev, curr - prev);
		v.push_back(tmp);
		prev = curr + 1;
		curr = str.find('-', prev);
	}
	v.push_back(str.substr(prev));

	vector<int> sums;
	for (int i = 0; i < v.size(); i++) {
		vector<int> v2;
		string str2 = v[i];
		prev = 0;
		curr = str2.find('+');
		while (curr != string::npos) {
			int num = stoi(str2.substr(prev, curr - prev));
			v2.push_back(num);
			prev = curr + 1;
			curr = str2.find('+', prev);
		}
		v2.push_back(stoi(str2.substr(prev)));

		int sum = 0;
		for (int j = 0; j < v2.size(); j++)
			sum += v2[j];
		sums.push_back(sum);
	}

	int ans = sums[0];
	for (int i = 1; i < sums.size(); i++)
		ans -= sums[i];
	cout << ans;

	return 0;
}

🥜 채점