[C++] 백준 온라인 저지 1541번 잃어버린 괄호 풀이

세준이는 +, -와 괄호를 이용해서 식을 만들었는데 실컷 만들고 나서 괄호를 지워버렸다. 

근데 세준이는 괄호를 다시 쳐서 이 식의 최솟값을 구하고 싶어짐...

괄호를 적당히 쳤을 때 얻을 수 있는 최솟값을 구하는 문제 

 

---

문제의 조건

 

1. +와 -로 구성된 식이 문자열로 주어진다. 

 

2. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 

 

3. 두 개 이상 연속해서 연산자(+, -)가 나타나지 않으며 5자리보다 많이 연속되는 숫자도 없다. 

 

4. 식에서 얻을 수 있는 최솟값을 구해서 출력

 

---

풀이 과정

 

처음 문제를 봤을 땐 풀이가 떠오르지 않아서 10분정도 고민하다가 질문 게시판을 봤습니다. 

거기서 -를 만나면 그 이후로 나오는 숫자는 모두 뺀다는 말을 보고 풀이 힌트를 얻었습니다. 

그러고 생각해보니까 모든 경우를 구해서 최솟값을 찾을 필요가 없었습니다. 

(처음엔 모든 경우의 수를 구하고 최솟값을 찾아야 하나 했었음)

 

그리디 알고리즘은 모든 경우를 탐색할 필요 없이 정답과 가장 가까워 보이는 경우를 탐색하면 되니깐...

처음부터 -를 만나면 당연히 빼야 하지만 

처음에 +를 만나면 무조건 더하는 경우밖에 없음

그리고 처음으로 만나는 - 다음 숫자들부터 +로 연결되어 있는 숫자들을 모두 괄호로 묶어서 먼저 계산한 다음에 

- 하면 결국은 어떤 경우보다 적은 값을 구하게 됩니다. 

 

그렇기 때문에 처음으로 -를 만나기 전까지는 더해주다가 -를 만난 이후로는 모든 숫자들을 빼주면 최솟값을 구할 수 있다

라는 결론을 얻었습니다. 

 

수포자라서 수학에 좀 무지했는데 똑똑하신 분들 덕분에 수학 공부도 하고 좋네용...ㅋㅋ

 

---

 

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(int argc, const char * argv[])
{
    string str;
    cin >> str;
    
    //숫자만 구분해서 배열에 따로 저장 
    string tmp = "";
    vector<int> numbers;
    for (int i = 0; str.length() > i; i++)
    {
        if ('0' <= str[i] && '9' >= str[i])
            tmp += str[i];
        else if ('+' == str[i] || '-' == str[i])
        {
            numbers.emplace_back(stoi(tmp));
            tmp.clear();
        }
    }
    //반복문을 거치고 나면 마지막 숫자는 배열에 저장되지 못 하고 남기 때문에 삽입 연산 한번 더 해줌 
    numbers.emplace_back(stoi(tmp));
    
    int answer = numbers.front(); //정답은 첫번째 숫자를 더해놓은 상태부터 시작 
    bool minus = false;
    for (int i = 1, j = 1; str.length() > i; i++)
    {
        if ('0' <= str[i] && '9' >= str[i])
            continue;
        else if ('-' == str[i])
        {
            minus = true; //- 만나면 빼기만 하도록 flag를 false로 바꿔줌 
            answer -= numbers[j++];
        }
        else
        {
            //-를 만나지 않았을 땐 더하고 만나고 나면 뺀다. 
            if (!minus)
                answer += numbers[j++];
            else
                answer -= numbers[j++];
        }
    }
    
    cout << answer;
    
    return 0;
}