(1541) 잃어버린 괄호

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

단계별로 풀어보기

23단계(그리디 알고리즘) 4번째

 

 

 

값을 최소로 하려면 빼기 뒤에 나오는 수가 최대가 되도록 해야 하며, 이는 빼기 뒤에 있는 더하기를 전부 괄호로 묶으면 된다.

빼기가 여러 개 나오더라도 제외하고 묶으면 첫 번째 빼기 뒤의 모든 수를 빼는 식을 만들 수 있으므로, 두 가지 경우로 단순화할 수 있다.

1) 식의 모든 연산자가 +일 땐 모든 수를 더한 값이 유일하게 가능한 해이다.

2) 식에 - 연산자가 있을 땐 -의 앞에 나오는 수들의 합에서 뒤에 나오는 수들의 합을 뺀 값이 가능한 최소값이다.

사실 더 큰 문제는 식이 그냥 문자열 하나로 주어지기 때문에 파싱을 해야 한다는 점이다(귀찮아서 예전 계정에서 썼던 파싱 코드를 가져왔다).

 

 

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int addsum(string str){
  int i=0, len=0, sum=0;
  for(int j=0;j<str.length();j++){
    if(str.find('+',j)==string::npos&&str.find('-',j)==string::npos){
      int x= stoi(str.substr(i, string::npos));
      sum+= x;
      break;
    }else if(str[j]=='+'||str[j]=='-'){
      int x= stoi(str.substr(i, len));
      sum+= x;
      i= j+1;
    }else{
      len++;
    }
  }
  return sum;
}

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

  if(s.find('-')==string::npos){
    cout << addsum(s);
  }else{
    int a= s.find('-');
    cout << addsum(s.substr(0,a))-addsum(s.substr(a+1));
  }
  
  return 0;
}