[PS 백준 - 3.7] 1541번: 잃어버린 괄호

문제 정보

백준 1541번 - 바로가기

• 난이도: 실버 2
• 알고리즘: 그리디 알고리즘

---

코멘트

처음에는 괄호는 한 쌍만 쳐야되는지 여러개 써도 되는지도 헷갈려서 상황 자체를 잘 이해하지 못했다. 아무 긴 수식을 써보니까 조금 이해가 됐다.

$50-35+30+20+30-25-20+20+40$
$(50)-{\color{Red}(35+30+20+30)}-{\color{Red}(25)}-{\color{Red}(20+20+40)}$

위처럼 마이너스가 나오면 앞뒤로 괄호를 열고, 닫아주면 된다. +는 괄호 를 열거나 닫는 거 없이 더하기만 하면 된다. 이렇게 하면 다음과 같은 규칙을 발견할 수 있다.

1. 수식에서 첫 번째 숫자에서 첫 번째 숫자를 제외한 모든 숫자를 빼면 그 값이 수식의 최솟값이다.

이러고 코드를 짰다가 "틀렸습니다" 가 나왔다. 다시 곰곰히 생각해보니까 +가 맨 앞에 나오는 경우를 생각하지 못했다.

$50+35+30-20+30-25+20+20+40$
${\color{Blue}(50+35+30)}-{\color{Red}(20+30)}-{\color{Red}(25+20+20+40)}$

이런 예시까지 고려해주면 아래와 같이 규칙을 정리할 수 있다.

2. 수식에서 첫 번째로 "-" 연산자가 나오기 전까지는 숫자들을 모두 더하고, 그 이후부터는 모두 빼면 그 값이 수식의 최솟값이다.

---

소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {

	string str;

	cin >> str;

	int result = 0;
	int idx = 0;

	vector<int> vec;

	string temp;
	while (true) {
		if (str[idx] == '-' || str[idx] == '+') break;
		temp += str[idx];
		idx++;
	}
	result = stoi(temp);

	// 빼기가 나오기 전까진 계속 더해주기
	while (idx < str.length()) {
		if (str[idx] == '+') {
			idx++;
			string temp2;
			int flag = 0;
			while (true) {
				if (str[idx] == '+') { flag = 0;  break; }
				if (str[idx] == '-') { flag = 1;  break; }
				temp2 += str[idx++];
				if (idx == str.length()) { flag = 1;  break; }
			}
			result += stoi(temp2);
			if (flag) break;
		}
		if (str[idx] == '-') break;
	}

	// 전부 다 빼버리면 되지 않나?
	while (idx < str.length()) {

		if (str[idx] == '-' || str[idx] == '+') {
			idx++;
			string temp2;
			while (true) {
				if (str[idx] == '-' || str[idx] == '+') break;
				temp2 += str[idx++];
				if (idx == str.length()) break;
			}
			vec.emplace_back(stoi(temp2));
		}
	}

	for (auto it = vec.begin(); it != vec.end(); it++) {
		result -= *it;
	}

	cout << result;

}