백준 1541번: 잃어버린 괄호

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

1541번: 잃어버린 괄호

0. 알고리즘 분류
수학, 문자열, 그리디 알고리즘, 파싱


1. 문제

2. 풀이
문제를 처음 읽고 이해를 못했다. 괄호를 쳐서 최솟값을 만들어라. 그럼 괄호를 숫자 사이에 치면, 곱셈으로 봐도 되는건가? "55-50+40"을 "5(5-50)+40"으로 봐야하는건가? 근데 그러면 예제로 준 값과 다른데. 조건이 제대로 명시되어있지 않아서 조금 헷갈렸다. 위와 같은 괄호를 쳐서 곱셈을 하는 것은 문제에서 요구하는 것과는 다르므로 쓰면 안된다. "55-(50+40)"이 요구하는 것이다.

단순히 뺄셈 뒤부터 다음 뺄셈 앞까지 숫자들을 다 더해서, 그 앞의 숫자에서 빼주면 된다. 필자는 상당히 무식하게 반복문과 조건문을 남발하여 풀었지만, 이보다 더 효율적인 코드는 많을 것이다.


3. 코드

#include <bits/stdc++.h> using namespace std; int main(void) { string s; cin >> s; int ans = 0; int i = 0; while (i < s.size() && '0' <= s[i] && s[i] <= '9') { ans = 10*ans + (s[i]-'0'); i++; } for (; i < s.size(); i++) { int temp = 0; if (s[i] == '+') { i++; while (i < s.size() && '0' <= s[i] && s[i] <= '9') { temp = 10*temp + (s[i]-'0'); i++; } ans = ans + temp; } else if (s[i] == '-') { i++; int sum = 0; while (i < s.size() && s[i] != '-') { if ('0' <= s[i] && s[i] <= '9') { int temp2 = 0; while (i < s.size() && '0' <= s[i] && s[i] <= '9') { temp2 = 10*temp2 + (s[i]-'0'); i++; } sum += temp2; } i++; } ans = ans-sum; } i--; } cout << ans; return 0; }