[C/C++] 백준 1541번 - 잃어버린 괄호(Greedy)

 

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

int len, tmp;
int sum = 0;
bool flag; // '-'가 등장했는지 체크
char str[51];

int main()
{
	cin >> str;
	len = strlen(str); //식의 길이

	for (int i = 0; i <= len; i++)
	{

		if (str[i] == '+' || str[i] == '-' || i == len) // '+','-'가 등장했거나 혹은 수식의 끝일때
		{
			if (flag == false) //'-'등장 이전 모든 값 양수화
			{
				sum += tmp;
				tmp = 0;
			}
			else // (flag == true), '-'등장 이후로 모든 값 음수화
			{
				sum -= tmp;
				tmp = 0;
			}

			if (str[i] == '-') flag = true; // '-'등장 시 체크
				
		}
		else // tmp변수에 값 누적
		{
			tmp *= 10;
			tmp += str[i] - '0'; // char 데이터를 정수로 변환
		}
	}

	cout << sum;
}

 

풀이 방법

3+2+6-3-5+4-2+10

위와 같은 식이 있다고 한다면 최적의 답은

= 3+2+6-(3)-(5+4)-(2+10)
= 11-24 = -13 

-13이 된다. 즉 '-'부호가 등장하면 그 이후의 식들은 괄호를 통해 모두 음수로 만들 수 있게 된다. 따라서 '-'가 등장할 때 flag라는 bool형 변수로 체크를 하고 '-'부호 등장 이전 값들은 모두 양수로, 이후 값들은 모두 음수로 변경하면 문제를 풀 수 있다.

 

www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호