[BOJ 1541] 잃어버린 괄호

여기서 주목해야 할 점은, 두 연산자가 반복해서 나오지 않는다는 것이다.

 

 

 

즉, 교대로 연산자가 나타나게 된다.

 

 

 

만약에 처음 연산자가 + 라면,

 

 

 

a + b - c + d - e + f,

 

 

 

여기서 최소의 값을 얻으려면,

 

 

 

a + b - (c + d) - (e + f)

 

 

 

형태로 괄호를 치면되고, 즉 b말고 c, d, e, f는 모두 빼주면 된다는 것이다.

 

 

 

나머지 경우인 처음 연산자가 - 라면,

 

 

 

a - b + c - d + e - f

 

 

 

a - (b + c) - (d + e) - f

 

 

 

a를 제외하고 나머지 b, c, d, e, f에 대해서 모두 빼주면 된다.

 

 

 

이 문제가 그리디인 이유는, 모든 경우를 보지 않고 +를 먼저 계산하게끔 괄호를 치면 정답을 구할 수 있기 때문이다.

 

 

 

해설코드(C++).

 

#include <iostream>
using namespace std;
 
string s;
string tmp = "";
bool flag = true;
int answer = 0;
 
int main() {
    cin >> s;
    for(int i = 0; i <= s.length(); i++){
        if(s[i] == '\0' || s[i] == '+' || s[i] == '-'){
            if(flag){
                answer += stoi(tmp);    
            }else
                answer -= stoi(tmp);
                
            if(s[i] == '-')
                flag = false;
                
            tmp = "";
            continue;
        }
        
        tmp += s[i];
    }
    
    cout << answer << endl;
    return 0;
}