[c++] 백준 1541 잃어버린 괄호

백준 단계별로 풀어보기 [그리디 알고리즘] 잃어버린 괄호

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

1541번: 잃어버린 괄호

 

[풀이]

수식에 -가 등장하면 그 다음부터 괄호를 쳐서 계속 뺄셈을 만드는 것이 결과값을 최소로 만드는 방식이다. 따라서 flag를 두어 - 가 등장하면 flag를 true로 바꾸어 값의 뺄셈을 하도록 하고, 그렇지않으면 값을 더하도록 한다. 계속 숫자가 나오면 자릿수를 키워야하므로 10을 곱해 누적시킨다.

 

[코드]

#include<iostream>
#include<algorithm>
#include<string>

int main() {
	int tmp = 0, sum = 0;
	bool flag = false;
	std::string s;
	std::cin >> s;

	for (int i = 0; i <= s.length(); i++) {
		if (s[i] == '+' || s[i] == '-' || i==s.length()) {
			if (flag == false) { // 양수면 덧셈
				sum += tmp;
				tmp = 0;
			}
			else { // 음수면 뺄셈
				sum -= tmp;
				tmp = 0;
			}
			if (s[i] == '-') {
				flag = true;
			}
		}
		else { // 숫자 누적.
			tmp *= 10;
			tmp += s[i] - '0';
		}
	}

	std::cout << sum;
}