1541_잃어버린 괄호_그리디 알고리즘

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

1541번: 잃어버린 괄호

문제

  세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

  그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

  첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.

출력

  첫째 줄에 정답을 출력한다.

 

---

문제 이해

  매우 간단히 숫자들의 덧셈, 뺄셈의 경우의 수 중 가장 작은 값을 출력하면 됩니다.

문제 해결

  일단 간단히 생각해보면, '-' 부호 뒤에 있는 덧셈들을 다 해준다음 그다음 마이너스를 해주는 것이 최고라고 생각합니다. '-' 부호가 등장하면 다음 '-' 부호가 등장하기 전까지 계속 더해주고 그걸 더해준다음 원래 앞에 있던 '-'를 계산한후 계속 이어 나가는 것입니다.

 

 

#include <iostream>
#include <string>
#include <algorithm>
#define MAX 51

using namespace std;

string input;
int sum = 0;
vector<int> v;

int main(void) {
	cin >> input;
	
	string temp = "";
	bool minus = false;
	for(int i = 0; i <= input.size(); i++) {
		if(input[i] == '+' || input[i] == '-' || input[i] == '\0') {
			if(minus) {
				sum -= stoi(temp);
			}
			else {
				sum += stoi(temp);
			}
			temp = "";
			if(input[i] == '-') {
				minus = true;
			}
			continue;
		}
		temp += input[i];
	}
	printf("%d\n", sum);
	
	return 0;
}