링크
https://www.acmicpc.net/problem/1541
문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
풀이
이 문제를 풀 때 2가지 어려운점이 있었는데
첫번째는 -가 나온 뒤로는 +든 -든 계속 -로 계산해야 최솟값이 나온다는 알고리즘을 알아내는 것이고
두번째는 입력받은 식에서 최솟값이 나오도록 부호를 고쳤는데 이 string 타입의 식을 어떻게 정수로 계산하느냐라는 것이었다.
먼저 식을 바꾸는 것은 string의 replace함수이다.
이렇게 바꾼 식을 인덱스 하나하나씩 검사하였다.
숫자는 char형 배열에, 검사중인 현재 인덱스 다음에 부호가 나타나면 cstdlib의 문자배열을 정수로 바꿔주는 atoi 함수를 이용하여 int형인 result값에 더하거나 빼준다.
코드
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
using namespace std;
int main() {
string N;
cin >> N;
int i = 0;
bool flag = false;
while (true) {
if (N[i] == NULL) {
break;
}
if (N[i] == '-' && !flag) {
flag = true;
}
else if (N[i] == '+' && flag) {
N.replace(i, 1, "-");
}
i++;
}
char tmp[5], count = 0;
int num;
bool cal = true;
int result = 0;
for (int j = 0; j < N.length(); j++) {
if (N[j] == '+') {
cal = true;
}
else if (N[j] == '-') {
cal = false;
}
else {
tmp[count++] = N[j];
if (N[j + 1] == '+' || N[j + 1] == '-' || N[j + 1] == NULL) {
num = atoi(tmp);
for (int k = 0; k < 5; k++) {
tmp[k] = NULL;
}
if (cal) {
result += num;
}
else {
result -= num;
}
count = 0;
}
}
}
cout << result;
return 0;
}
