[알고리즘] C++ 백준 1541 잃어버린 괄호

 

백준 1541

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

1541번: 잃어버린 괄호

 

풀이 전 나의 생각

 

이 문제는 괄호를 적절하게 사용하여 최소값을 구하는 문제다.

예를 들어 55-50+40-30+20 이란 식이 있다고 가정하자.

최소값을 구하기 위해선 음수값을 최대로 올려야 한다. -> '-' 와 관련된 부분을 건들이면 될 것이다.

 

그럼 '-' 뒤에 있는 값들을 더해서 음수를 크게 만들어 보면  55 - (50 + 40) - (30 + 20) 이란 결과가 나오게 된다.

결론은 '-' 뒤에 있는 숫자들을 모두 빼주면 최소값은 쉽게 구할 수 있다는 것이다.

 

좀 더 설명하자면  55 - (50 + 40) - (30 + 20) == 55 - 50 - 40 - 30 - 20 이기 때문에 '-' 가 처음으로 시작 한 이후로 생긴 값들을 모두 빼주면 최소값이 나오게 된다.

 

괄호를 알맞게 쳐서 나오는 결과 값 == '-'가 나온 다음 값들을 모두 빼준 값 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>


using namespace std;


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

	string input = "";
	string num = "";
	int res = 0;
	bool minus = false;
	cin >> input;

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

	cout << res;
}