[c++] 백준 1541, 잃어버린 괄호

백준 1541

알고리즘 분류 : greedy algorithm (그리디 알고리즘)

괄호가 없는 수식에 괄호를 적절히 쳐, 수식의 값을 최소로 만드는 문제다.

이 문제를 해결하기 위해서는, 어떤 경우에 값이 최소가 되는지에 대한 파악이 필요하다.

1. 55-50+40 -> 55-(50+40)
2. 10+20-30+40-50 -> 10+20-(30+40)-50

앞의 두 경우는 각각의 수식에서 값이 최소가 되는 경우다. 살펴보면, -부호가 등장한 이후의 숫자들은 모두 뺄셈을 해줘야 값이 최소가 됨을 확인할 수 있다.

isminus가 true인 경우, result-=stoi(num)
isminus가 false인 경우, result+=stoi(num)

반복문은 i=input.size()일 때까지 진행하는데, 이유는 마지막 숫자에 해당하는 연산까지 수행하기 위해서다.

#include <iostream>
#include <string>

using namespace std;

int main(){
	string input,num;
	int result=0;
	bool isminus=false;
	cin >> input;
	
	for(int i=0; i<=input.size(); i++){
		if(input[i]=='+'||input[i]=='-'||i==input.size()){
			if(isminus){
				result-=stoi(num);
				num="";
			}
			else{
				result+=stoi(num);
				num="";
			}
		}
		else{
			num+=input[i];
		}
		if(input[i]=='-'){
			isminus=true; //input[i]가 '-'인 경우, isminus=true;
		}
	}
	
	cout << result;
}