문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
const int MAX=51;
string cal;
char opt[MAX];
int num[MAX]={0};
bool isMinus;
int main() {
cin >> cal; // 식
int num_idx=0, opt_idx=0, ans=0;
isMinus=false;
for(int i=0;i<cal.length()+1;i++){
if (cal[i] == '-' || cal[i] == '+' ) {
opt[opt_idx] = cal[i];
num_idx++;
opt_idx++;
}
else if (cal[i] == '\0') {
num_idx++;
}
else{
num[num_idx] = num[num_idx] * 10 + (cal[i] - '0');
}
}
ans += num[0];
for(int i=0;i<opt_idx;i++){
if(opt[i]=='-'){
isMinus=true;
}
if(isMinus){
ans -= num[i+1];
}
else{
ans += num[i+1];
}
}
cout << ans;
return 0;
}
string 변수를 만들고 거기에 식을 받은 뒤, (C++은 그냥 cin으로 받아줄 수 있다. 이밖에도 getline(cin, 변수이름)으로 받을 수 있다. 그 뒤, 연산자 인덱스 따로, 숫자 인덱스 따로 만들어서 -나 + 연산자일 경우 연산자 배열에 넣어주고 숫자일 경우 숫자 배열에 넣어 주었고 특히, 마지막 문자열의 마지막 부분인 '\0' 조건문 또한 추가해줘서 총 숫자의 개수를 정확히 해주었다. 이때, 배열.length()에서 +1을 해주어야한다.
중간에 -가 있는 경우 결국 최솟값은 뒷 부분 모든 부분이 -가 된다.
예) 50+10-20+15-30+10 ⇒ 50+10-(20+15)-(30+10) = 50+10-20-15-30-10