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

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

---

그리디 알고리즘을 사용해서 풀면 된다.

말이 알고리즘이지 실버쯤 되는 그리디 문제는 무지성으로 풀어도 풀린다..

 

값을 최소로 만들려면, "-" 뒤에 오는 값이 최대가 되도록 괄호를 쳐주면 된다!

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
	string s;
	string buf = "";
	cin >> s;
	int len = s.length();
	int result = 0;
	bool is_minus = false;
	for (int i = 0; i <= len; i++) {
		if (s[i] == '-' || s[i] == '+' || i == len) {
			if (is_minus) {
				result -= stoi(buf);
				buf = "";
			}
			else {
				result += stoi(buf);
				buf = "";
			}
		}
		else {
			buf.push_back(s[i]);
		}
		if (s[i] == '-') {
			is_minus = true;
		}
	}
	cout << result;
	return 0;
}

 

알고리즘 분류에 문자열과 파싱이 있는걸 보고 잠시 어지러웠지만,

C에서 C++로 건너온 우리에게는 string 자료형과 stoi라는 몹시 뛰어난 편의성의 함수가 있다!! (감동의 도가니)

 

괄호를 쳐서 최솟값을 만든다는게, "-" 뒤의 값들을 최대가 되게 묶어주면 된다고 이야기했었다.

묶어준다는건, 묶은 괄호 내의 "+" 연산자를 모두 "-"로 바꾼다는 뜻이기도 하다.

---