[백준] 1541번 잃어버린 괄호

1541 잃어버린 괄호

문제

---

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

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

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

입력

---

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

출력

---

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

---

풀이)

모든 경우를 확인하는 brute force 문제가 아닌, greedy 문제.

 - 나올 때마다 괄호쳐서 분리한 뒤, 계산하면 최소값이 되는 문제이다. 왜 그런지는 예시를 보자.

예시)

1+2-3+7-10 일 경우 최소값은 1+2-(3+7)-(10) = -17  ,      최소값의 식 -> 1+2-3-7-10

10+10-10-10+10 일 경우 최소값은 10+10-(10)-(10+10) = -10 ,     최소값의 식 -> 10+10-10-10-10

4+4-2+2+2 일 경우 최소값은 4+4-(2+2+2) = 2  ,      최소값의 식 -> 4+4-2-2-2

위를 보고 알 수 있는 점은 -마다 괄호를 치기 때문에

한 개의 -로 인해 괄호가 시작되면, 그 뒤에 오는 모든 수는 빼야하는 수임을 알 수 있다.

이를 이용해서 코드를 작성하면 된다.

주의점

숫자는 0으로 시작될 수 있다 -> 02  = 2  or  0043  = 43 이런식으로

코드)

#include <stdio.h>
#include <string>
#include <iostream>
 
using namespace std;
 
int main() {
    string s;
    cin >> s;
    s += '.';//마지막 숫자까지 계산하기 위해 추가,문자열의 끝임을 표시
    string temp = "";
    bool galho = false;
    int result = 0;
    for (int i = 0; i < s.length(); i++) {
        
        if (s[i] == '+' || s[i] == '-' || s[i] == '.') {
            if (galho) result -= stoi(temp);
            else result += stoi(temp);
 
            temp = "";
            if (s[i] == '-') galho = true; //괄호 시작
            continue;
        }
        temp += s[i];
    }
    printf("%d", result);
    return 0;
}