백준 1541번: 잃어버린 괄호 (C++)

문제 링크 : https://www.acmicpc.net/problem/1541

 

너무 간단한 문자열 문제이다.

 

 

<전체적인 알고리즘>

1. 수를 최소로 만드려면 '-'로 최대한 많은 수를 묶어야 한다는 것을 알 수 있다.

2. '-'가 나오기 전까지는 '-'로 묶을 수가 없으니 당연히 더하는 방법밖에는 없다. 결국 '-'가 나오기 전까지는 모두 더해준

    다.

3. '-'나온 후에는 모두 빼면 된다는 것을 쉽게 알 수 있다. '-'가 한번이라도 나온 후에는 모두 음수로 만들 수 있다.

   ex) 1+2-3+4+5+6+7    ->  1+2-(3+4+5+6+7)

   ex) 1+2-3+4+5-6+7     -> 1+2-(3+4+5)-(6+7) 

 

 

<전체 코드>

#include<iostream>
#include<string>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	string str;
	cin >> str;
	
	int sum = 0;
	int tmp = 0;
	bool flag_minus = false;

	for (int i = 0; i < str.size() ;i++)
	{
		if (str[i] == '-' || str[i] == '+')
		{				
			if (flag_minus)sum -= tmp;  // '-' 가 한번이라도 나온 후에는 전부 빼주기
			else sum += tmp;        // '-' 가 나오기 전까지는 더해주기
			
			tmp = 0;       //tmp수를 다시 리셋
			if (str[i] == '-')flag_minus = true;  //-가 나오면 flag를 true로 바꿔줌
		}
		else  //숫자가 연속해서 나오는동안은 한 수로 붙이기
		{
			tmp *= 10;
			tmp += str[i] - '0';  // 아스키코드 이용
		}
	}

    //마지막남은 숫자도 처리해주어야 한다
	if (flag_minus)sum -= tmp; 
	else sum += tmp;

	printf("%d ", sum);

	return 0;
}

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.