백준 1541번: 잃어버린 괄호 (C++)

문제 링크 : https://www.acmicpc.net/problem/1541

 

너무 간단한 문자열 문제이다.

 

 

<전체적인 알고리즘>

1. 수를 최소로 만드려면 '-'로 최대한 많은 수를 묶어야 한다는 것을 알 수 있다.

2. '-'가 나오기 전까지는 '-'로 묶을 수가 없으니 당연히 더하는 방법밖에는 없다. 결국 '-'가 나오기 전까지는 모두 더해준

    다.

3. '-'나온 후에는 모두 빼면 된다는 것을 쉽게 알 수 있다. '-'가 한번이라도 나온 후에는 모두 음수로 만들 수 있다.

   ex) 1+2-3+4+5+6+7    ->  1+2-(3+4+5+6+7)

   ex) 1+2-3+4+5-6+7     -> 1+2-(3+4+5)-(6+7) 

 

 

<전체 코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include<iostream> #include<string>   using namespace std;   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);       string str;     cin >> str;           int sum = 0;     int tmp = 0;     bool flag_minus = false;       for (int i = 0; i < str.size() ;i++)     {         if (str[i] == '-' || str[i] == '+')         {                           if (flag_minus)sum -= tmp;  // '-' 가 한번이라도 나온 후에는 전부 빼주기             else sum += tmp;        // '-' 가 나오기 전까지는 더해주기                           tmp = 0;       //tmp수를 다시 리셋             if (str[i] == '-')flag_minus = true;  //-가 나오면 flag를 true로 바꿔줌         }         else  //숫자가 연속해서 나오는동안은 한 수로 붙이기         {             tmp *= 10;             tmp += str[i] - '0';  // 아스키코드 이용         }     }       //마지막남은 숫자도 처리해주어야 한다     if (flag_minus)sum -= tmp;     else sum += tmp;       printf("%d ", sum);       return 0; }

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.