https://www.acmicpc.net/problem/1541
문제
> 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
> 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
> 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
> 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다.
> 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다.
> 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.접근
식에 괄호를 임의로 넣어 값을 최소로 만들기 위해선 빼기연산을 제일 많이 했을 때 최소 값을 가질 수 있다.
그래서 뺴기연산인 -문자가 나온곳 부터 다시 -가 나올때 아니면 문자열이 끝날때 까지 괄호로 싹 묶어서 전부 마이너스 부호를 가지게해서 빼주면 된다.
예를들어 55-30+10+20-40+24+23-39 라고하면 -문자를 기준으로 55-(30+10+20)-(40+24+23)-39이렇게 묶어주면 최소값을 얻을 수 있다.
문제해결
> 문자열 s를 입력받고 +와 -를 구분해 연산을 다르게 해줄 sign부울 변수를 선언해 부호를 나타내준다.
> +나-, 문자열의 끝을 만났을 때 지금까지의 숫자를 따로 저장해줄 string변수 str을 공백으로 선언해준다.
최종 식의 값을 저장할 sum변수도 선언한다.
> 문자열을 인덱스로 문자로 나눠 봐야하므로 0부터 문자열의 사이즈 까지 반복문을한다. 마지막으로 나온 수 까지 계산을 해줘야 하기 때문에 문자열의 끝을 만났을 때를 위해 s.size()까지 반복문을 한다.
> 만약 i가 s.size()로 인덱스가 끝나거나, + 또는 -문자를 만났다면 sign이 true냐 false냐에 따라 연산을해준다.
> +만 만났을 때 false인 상태고 -를 만나면 이제 괄호로 전부 뺴준다라는 식으로 가줄 거기 때문에 true로 준다.
> sign에 따라 true면 -를 만났기 때문에 sum에 지금까지 str에 담긴 문자들 즉, 수를 정수로 변환해 뺴준다.
sign이 false면 아직 +만 만난거기 때문에 다 더해준다.
> 조건문 밖은 아직 +,-,끝을 안만난것이므로 str에 계속 문자를 추가해 계산해줄 수를 저장해준다.
> 최종적으로 계산이 끝나고 sum에 남아있는값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string s;
cin >> s;
bool sign = false; //부호가 +일떄
string str = "";
int sum = 0;
for (int i = 0; i <= s.size(); i++)
{
if (i == s.size() || s[i] == '+' || s[i] == '-')
{
sign ? sum -= stoi(str) : sum += stoi(str);
str = "";
if (s[i] == '-') sign = true;
continue;
}
str += s[i];
}
cout << sum << '\n';
}
후기
중간중간 문자열에 개입해 ()를 넣어 이를 수식으로 변환해 계산을 한다던가, 수만 추출해서 내가 임의로 계산한다던가 했지만 다 예외가 생기고 말이 안되는 과정이었다.
문제의 최솟값을 계속 보다가 최소가 되려면 뺴기연산을 최대한 해줘야한다는걸 알았다.
직접 괄호를 쳐주는게 아닌 -뒤에 나오는 숫자는 전부 괄호로 묶어진걸로 치자 라는 생각으로 -를 만나면 싹다 수를 빼주도록 했다.
어려웠지만 생각보다 단순했다.
