[BOJ/C++] 1541 잃어버린 괄호

그리디 알고리즘을 이용하여 문제를 해결할 수 있습니다.

최솟값을 만들기 위해선 음수를 가장 크게 만들어야합니다.

마이너스 부호를 시작으로 이후 나오는 덧셈을 괄호를 이용해 모두 묶어주면 가장 큰 음수를 얻을 수 있습니다.

즉, 마이너스 부호 이후에 나오는 값들을 모두 빼주면 최솟값을 얻을 수 있습니다.

1. 마이너스 부호가 하나도 안나온 경우 -> 모두 더한 값이 최솟값
2. 마이너스 부호가 1개 이상 나온 경우 -> 마이너스 부호 이후의 값을 모두 빼주면 최솟값

// boj s2 1541
// 잃어버린 괄호

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	string input;
	cin >> input;

	int result = 0;
	string num;
	bool flag = false;

	for(int i=0; i<=input.size(); i++)
	{
		if(input[i]=='-' || input[i]=='+' || i==input.size())
		{
			if(flag)
			{
				result -= stoi(num);
				num = "";
			}
			else
			{
				result += stoi(num);
				num = "";
			}
		}
		else
		{
			num += input[i];
		}

		if (input[i] == '-' )
			flag = true;
	}

	cout << result;
	
	return 0;
}