[그리디] 잃어버린 괄호(15410)(C++)

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

1541번: 잃어버린 괄호

 

 

1. 문제 개요

 

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

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

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

 

 

2. 입출력

 

 

3. 문제 풀이

 

 

식의 값이 최소가 되기 위해서는 빼주는 값이 최대한 많아야 한다.

55-50+40

다음과 같은 식이 있을 때, 50과 40을 괄호로 묶어주면 55-90이 되기 때문에 식이 최소가 될 수 있다.

55-(50+40)

 따라서 연산자가 - 인 경우 그 뒤로 + 연산자 뒤의 숫자는 모두 괄호 안에 넣게되면 식의 값을 최소화 할 수 있다.  

55-(50+40)-(60+70+80+50)-(30+40+70)

 

 

4. 전체 코드

#include <iostream>

using namespace std;

int main(void) {
    string equation, tempStr="";
    int result = 0;
    bool isMinus = false;
    
    cin >> equation;
    equation += "#"; // string의 끝을 표시
    
    for(int i=0;i<equation.length();i++) {
        if(equation[i]=='-'||equation[i]=='+'||equation[i]=='#') { // 문자열의 끝이거나 연산자인 경우
            if(isMinus) result -= stoi(tempStr);
            else {
                if(equation[i]=='-') isMinus = true;
                result += stoi(tempStr);
            }
            tempStr = "";
        } else { // 숫자인 경우
            tempStr += equation[i];
        }
    }
    cout << result;
}