코딩 테스트 준비! (백준)/GREEDY

[그리디]백준 1541번 잃어버린 괄호(C++)

lee-soo 2025. 5. 15. 15:58

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

 

문제는 간단하다

 

최소가 되면 됨

 

잘 생각해봐라

-가 나온 이후에

+가 나온다면?
-앞에 괄호를 쳐줘서 모든 + 들을 다 더한 후 음수로 바꿀 것이다

 

그렇다면

 

-가 나온 이후에

+가 나오고

 

또 -가 나오면?

 

그냥 또 빼주면 된다

 

그니까

 

-가 1개라도 나오면 그 이후의 수는 모두 -로 바꿔주는 것이 최소이다.

#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    cin >> s;
    string temp;

    int result = 0;
    char trigger = '+';
    int first = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] != '+' || s[i] != '-')
            temp.push_back(s[i]);

        if (first == 0 && (s[i] == '+' || s[i] == '-'))
        {
            result += stoi(temp);
            first = 1;
            temp = '0';
            trigger = s[i];
        }

        if ((s[i] == '+' || s[i] == '-') && trigger == '-')
        {
            result -= stoi(temp);

            temp = '0';
        }

        if (s[i] == '-' && trigger == '+')
        {
            result += stoi(temp);
            temp = '0';
            trigger = '-';
        }
        if (s[i] == '+' && trigger == '+')
        {
            result += stoi(temp);
            temp = '0';
        }

        if (i == (s.length() - 1) && trigger == '-')
        {
            result -= stoi(temp);
        }
        if (i == (s.length() - 1) && trigger == '+')
        {
            result += stoi(temp);
        }
    }
    cout << result;
}
 
대충 이렇게 풀었는데
그냥 -가 나왔으면
 
bool 변수 하나만들고 true바꾸고
뒤에 나오는 모든값을 - 로 해주면 더쉬울듯