[BOJ]1541번: 잃어버린 괄호 (c++)

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

1541번: 잃어버린 괄호

 

그리디

#include <iostream>
#include <vector>

using namespace std;

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

	// 입력
	string line;
	cin >> line;

	// 문자열을 파싱하여 숫자는 nums벡터에
	// 연산자는 +이면 signs벡터에 +1을, -이면 -1을 signs벡터에 push한다
	vector<int> nums;
	vector<int> signs;
	signs.push_back(1);
	int num = 0;
	for (int i = 0; i < line.size(); ++i)
	{
		char c = line[i];
		if (c == '+' || c == '-')
		{
			nums.push_back(num);
			num = 0;

			signs.push_back((c == '+') ? 1 : -1);
		}
		else
		{
			num *= 10;
			num += line[i] - '0';
		}
	}
	nums.push_back(num);

	
	/*
		식의 결과를 최소로 만들기 위해서는
		- 연산자 이후를 모두 괄호로 묶어주어야 한다.
		즉 -연산자가 한번이라도 나온다면 그 뒤의 수는 모두 음수라고 판단할 수 있다.
	*/
	int res = 0;
	bool minus = false;
	for (int i = 0; i < nums.size(); ++i)
	{
		if (signs[i] == -1)
		{
			minus = true;
		}

		if (minus)
		{
			res -= nums[i];
		}
		else
		{
			res += nums[i];
		}
	}

	cout << res;


	return 0;
}

 

 

-연산자 이후의 숫자들은 음수로 취급해도 무방하다!

는 아이디어만 떠오른다면 무난히 풀 수 있는 문제이다.

그리디 문제가 늘 그렇듯이 ㅜㅜ

 

 

 

아래 코드는 가장 처음에 AC받은 코드이다.

"-연산자 이후의 숫자들은 다음 -연산자가 나올때까지 하나의 숫자에 더했다가 답에서 빼준다"

는 의도였는데 위에 올린 코드보다 직관적이지 못하다.

 

#include <iostream>
#include <vector>

using namespace std;

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

	string line;
	cin >> line;

	vector<int> nums;
	vector<char> ops;
	int num = 0;
	for (int i = 0; i < line.size(); ++i)
	{
		if (line[i] >= '0' && line[i] <= '9')
		{
			num *= 10;
			num += line[i] - '0';
		}
		else 
		{
			nums.push_back(num);
			ops.push_back(line[i]);
			num = 0;
		}
	}
	nums.push_back(num);



	int res = nums[0];
	int tmp = 0;

	bool flag = false;
	for (int i = 0; i < ops.size(); ++i)
	{
		if (ops[i] == '-')
		{
			res -= tmp;
			tmp = nums[i + 1];
			flag = true;
		}
		else
		{
			if (flag)
			{
				tmp += nums[i + 1];
			}
			else
			{
				res += nums[i + 1];
			}
		}
	}
	res -= tmp;

	cout << res;


	return 0;
}