백준 1541 - 잃어버린 괄호

문제 요약

주어진 식에 괄호를 적절히 쳐서 식의 값을 최소로 만드시오.

가장 처음과 마지막은 숫자이며 두 개 이상의 연산자가 나타나지 않으며 5자리보다 많이 연속되는 숫자는 없다.

 

 

접근

1. -뒤에 무조건 괄호를 넣어서 계산한다. 

2.1. -가 나오면 괄호를 닫고 그 후 -를 계산한다.

2.2 +가 나오면 괄호를 유지한 채로 큰 수를 만들어 -를 계산한다. 

 

 

코드

#define _CRT_SECURE_NO_WARNINGS

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


string str;
int N;
int main() {

	cin >> str;

	int result = 0;
	string num;
	bool isMinus = false; //-기호가 나왔는지 체크

	for (int i = 0; i <= str.size(); i++) {
		if (str[i] == '+' || str[i] == '-' || i == str.size()) { 
			if (isMinus) { //연산자가 무엇이든 그 전에 -가 한번 나왔다면 빼기 계산
				result -= stoi(num); //int형을 string으로 변환 string 헤더파일필요
				num = "";
			}
			else {
				result += stoi(num);
				num = "";
			}
		}
		else {
			num += str[i]; 
		}
		if (str[i] == '-') { //-식이 나오면 isMInum를 true로
			isMinus = true;
		}


	}

	cout << result;




	return 0;
}

 

 

풀이

접근이 비슷하긴 했지만 조금 더 간단하게 정리를 했어야한다. 괄호를 마음대로 칠 수 있는 순간부터 -가 나온 뒤의 +는 모두 -로 바뀐다는 것을 알아차리면 코드를 짜기 수월하다.  Greedy 알고리즘을 사용하여 눈 앞에 당장 -가 나온 것부터 생각하며 문제를 풀면 된다.

 

고찰

처음 접근은 문자열 식에서 괄호를 진짜 넣어야 하나부터 시작해서 굉장히 쉬운 문제를 굳이굳이 어렵게 돌아갈뻔했다.

문제가 원하는 바를 정확히 파악해서 그 결과를 도출해내는 가장 쉬운 방법을 고민해보도록 해야겠다.