(백준/C++) 1541_잃어버린 괄호

잃어버린 괄호 문제는 정렬을 사용하지 않아도 풀 수 있는 탐욕 알고리즘 문제입니다.

탐욕 알고리즘(Greedy Algorithm)이란, 매 순간 최적이라고 생각되는 방법을 선택하는 방식으로 문제를 해결하는 알고리즘입니다.

즉, 다른 경우의 수를 생각하지 않고 현 문제에서 가장 좋아 보이는 것을 선택하다 보면 문제가 풀리는 알고리즘 입니다.

1541번: 잃어버린 괄호 (acmicpc.net) 문제는 괄호가 없는 수식에 괄호를 적절히 넣었을 때, 가장 작은 수를 만들 수 있는 방법을 찾는 문제입니다.

이 문제의 핵심은 ‘+’, ‘-’만으로 이루어져 있다는 점입니다.

---

접근법

탐욕 알고리즘 문제는 대부분이 쉽게 풀리는 문제들입니다.

이 문제의 핵심은 수식의 수를 최소로 만드는 수식을 찾는 것입니다.

1) ‘+’에 ‘-’ 괄호를 씌우면 ‘-’가 된다.

이 문제의 수식은 ‘+’, ‘-’만으로 이루어져 있습니다.

여기에서 간단한 수학을 떠올려보면, 음수와 양수를 곱하면 음수가 된다는 사실이 있습니다.

따라서 괄호를 묶을 때, ‘-’ 기호 사이에 나오는 모든 수를 괄호로 묶어버리면, ‘-’ 기호 이후의 모든 수가 음수가 됩니다.

---

풀이

사실, 표현을 ‘-’ 기호 사이에 모든 수를 묶는다고 했는데, 이렇게 표현한 이유가 ‘-’에 ‘-’를 곱해버리면 ‘+’가 되기 때문입니다.

따라서, 이 점을 생각해서 ‘-’ 기호 이후의 모든 수를 음수로 취급하기만 한다면, 이 문제를 간단히 풀어버릴 수 있습니다.

즉, stringstream으로 문자열을 읽고 int 로 변환했을 때 음수였다면, 이후에 나오는 모든 수를 음수로 취급해주면 됩니다.

#include <iostream>
#include <sstream>
using namespace std;

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

	int result = 0;
	
	string exp;
	getline(cin, exp);

	stringstream ss(exp);
	bool isMinus = false;
	while (!ss.eof())
	{
		int num;
		ss >> num;
		
		// int로 받아오면서 음수 이후의 모든 숫자는 음수로 취급한다.
		if (num < 0) isMinus = true;
		if (isMinus && num > 0) num *= -1;

		result += num;
	}

	cout << result;
}