[baekjoon 1541] 잃어버린 괄호 (그리디, 문자열, 수학) (C++)

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

입력값은 양수와 +, -로 주어진다. 괄호를 이용해서 수식의 결괏값이 최솟값이 되어야 한다.

나는 케이스를

1. +만 있는 경우 -> 다 더하면 된다.

2. -만 있는 경우 -> 다 빼면 된다.

3. -와 +가 섞인 경우 -> +가 나오는 경우는 더해주고, -가 나오면 그 이후에 나오는 +는 빼주었다.

 

50 - 40 + 30 => 그냥 계산은 40이고, - 이후 괄호를 쳐서 계산하면 50-70으로 -20인 최솟값이 나온다.

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string s;
vector<int> vn;
vector<char> vc;


int main() {
	cin >> s;

	string num = "";
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != '+' && s[i] != '-') {
			num += s[i];
		}
		else {
			vn.push_back(stoi(num));
			num = "";
			vc.push_back(s[i]);
		}
	}
	vn.push_back(stoi(num));

	int result = vn[0];
	int temp = 0;
	for (int i = 1; i < vn.size(); i++) {
		if (vc[i - 1] == '+') {
			if (temp != 0) {
				temp += vn[i];
			}
			else {
				result += vn[i];
			}
		}
		else { // -일때
			if (temp != 0) {
				result -= temp;
				temp = 0;
			}
			if (temp == 0) {
				temp += vn[i];
			}
		}
	}
	if (temp != 0) {
		result -= temp;
	}

	cout << result;
}

나는 진짜 생각의 흐름대로 문제를 풀었다.. 숫자와 연산자를 나눠주고, for문을 돌면서 +와 - 의 경우를 나눠서 풀었다.

풀고 나서 사람들의 결과물을 보니까 엄청 간단하게 풀었다.

 

위 케이스에서 3번 논리를 이용해서 간단하게 풀었는데, +가 나오면 그냥 더해주고 -가 나오면 그 이후 수는 다 빼줬다.

int result = vn[0];
	int temp = 0;
	for (int i = 1; i < vn.size(); i++) {
		if (!temp) {
			if (vc[i - 1] == '+')
				result += vn[i];
			else {
				temp = 1;
				result -= vn[i];
			}
		}
		else {
			result -= vn[i];
		}
	}

계산 부분을 이렇게 줄일 수 있었다. -가 나온 이후는 다 빼주면 된다.