백준 1541 잃어버린 괄호

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 수식을 입력받았을때 괄호를 적절히 쳐서  최소의 값을 만드는 값을 출력하는 문제입니다.

 

부호는 +와-밖에 나오지 않으므로 -가 한번이라도 나오면 그 뒤부분은 모두 -로 처리할 수 있음을 알 수 있습니다. 

 

예를들어 2+3-4+5-6+2 라면 -4가 나온순간 4 와 5를 묶고 6과 2를 묶으면 모두 -로 처리 할 수 있습니다.

 

따라서 그리디하게 처음 - 가 나올때까지의 숫자들과 그 이후 숫자들을 나누어서 서로 합해주면 답을 구할 수 있습니다.

 

다음은 코드입니다.

 

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

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int ans = 0;
	string str;
	cin >> str;
	string cur="";
	char curch='+';
	for(int i = 0; i < str.size(); i++) {
		if(str[i] == '+' || str[i] == '-') {
			if(curch == '-') {
				ans -= stoi(cur);
				cur="";
			}
			else {
				ans += stoi(cur);
				cur="";
				if(str[i] == '-')
					curch = '-';
			}
		}
		else
			cur += str[i];
	}
	if(curch == '-')
		ans -= stoi(cur);
	else
		ans += stoi(cur);
	cout<<ans;
	return 0;
}