C++ / 1541 / 잃어버린 괄호 ( 그리디 알고리즘 )

https://www.acmicpc.net/problem/1541

문제 요약

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었습니다.

그리고 나서 세준이는 괄호를 모두 지웠습니다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 합니다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성해야합니다.

문제 풀이

1. 문자열을 입력받습니다.

2. 입력받은 문자열을 인덱스 별로 확인하는데 '0' ~  '9' 사이면 임시 문자열에 저장합니다.

3. '0' ~ '9' 밖이면 '-' 나 '+'기 때문에 저장했던 임시 문자열을 숫자로 바꿔줍니다. 

4. 임시 문자열 마지막 인덱스부터 - '0'을 하고 자릿수 많큼 ( c 변수는 10씩 증가 이는 자릿수를 의미 ) 곱해주고 현재 숫자를 저장할 변수에 저장합니다.

5. '+'면 현재 숫자를 더합니다.  '-'면 check변수를 true로 하여 이후로나오는 모든 숫자를 빼줍니다.

6. 그렇게 만들어진 결과를 출력합니다.

주의할 점

오랜만에 그리디 문제를 풀어보았는데, 생각보다 잘 안풀려서 당황스러웠습니다.

 

아래 코드는 처음에 풀었던 코드입니다.

밑의 코드는 정답을 출력하긴 합니다.숫자 들을 임시 배열을 만들어, 나올 수 있는 모든 식을 계산하여 정렬하여 가장 작은 값을 출력하도록 하였는데이는 이 문제에서 바란 답이 아니고 너무 비효율적인 방법이라 틀렸던 것 같습니다.

 

모든 경우의 수를 보지 않더라도 가장 작은 답은 -기준으로 뒤에 값을 남은 수에 빼주면 가장 작은 값이 나오는 간단한 방법이 있었습니다.

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

int j = 0, a = 0, sum = 0, temp = 0;
string s;
vector<int>v, ans;
vector<char> t, p;
int main()
{
	cin >> s;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] >= '0' && s[i] <= '9')
		{
			t.push_back(s[i]);
		}
		else
		{
			p.push_back(s[i]);
			int c = 1;
			a = 0;
			for (int k = t.size() - 1; k >= 0; k--)
			{
				a += (t[k] - '0') * c;
				c *= 10;
			}
			t.clear();
			v.push_back(a);
		}

		if (i == s.length()-1)
		{
			int c = 1;
			a = 0;
			for (int k = t.size() - 1; k >= 0; k--)
			{
				a += (t[k] - '0') * c;
				c *= 10;
			}
			t.clear();
			//cout << a << " \n";
			v.push_back(a);
		}
	}
	//cout << v.size();
	if (v.size() <= 2)
	{
		for (int i = 0; i < v.size(); i++)
		{
			if (i == 0)
			{
				sum += v[i];
			}
			else
			{
				if (p[i - 1] == '+')
				{
					sum += v[i];
				}
				else
				{
					sum -= v[i];
				}
			}
		}
		ans.push_back(sum);
		//cout << " adasdf";
	}
	else
	{
		for (int j = 2; j < v.size(); j++)
		{
			for (int i = 0; i <= v.size() - j; i++)
			{
				for (int k = i; k < i + j; k++)
				{
					if (k == i)
					{
						sum += v[k];
					}
					else
					{
						if (p[k - 1] == '+')
						{
							sum += v[k];
						}
						else
						{
							sum -= v[k];
						}
					}

				}
				if (i != 0)
				{
					for (int l = 0; l < i; l++)
					{
						if (l == 0)
						{
							if (p[0] == '+')
							{
								sum = v[0] + sum;
							}
							else
							{
								sum = v[0] - sum;
							}
						}
						else
						{
							if (p[l - 1] == '+')
							{
								sum += v[l];
							}
							else
							{
								sum -= v[l];
							}
						}
					}
				}
				if (i + j < v.size())
				{
					for (int l = i + j; l < v.size(); l++)
					{
						if (p[l - 1] == '+')
						{
							sum += v[l];
						}
						else
						{
							sum -= v[l];
						}
					}
				}

				ans.push_back(sum);
				sum = 0;
			}
		}
		sort(ans.begin(), ans.end());
	}
	
	cout << ans[0];

	return 0;
}

코드

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

int j = 0, a = 0, sum = 0, temp = 0;
int check = 0;
string s;
vector<int>v;
vector<char> t;
int main()
{
	cin >> s;

	for (int i = 0; i < s.length(); i++)
	{
		// 숫자면 임시저장
		if (s[i] >= '0' && s[i] <= '9')
		{
			t.push_back(s[i]);
		}
		else // 숫자가 아니면 임시저장한 문자열 숫자로 변환
		{
			// 자릿수
			int c = 1;
			a = 0;
			for (int k = t.size() - 1; k >= 0; k--)
			{
				a += (t[k] - '0') * c;
				c *= 10;
			}
			t.clear();
		}

		// 마지막 인덱스면 임시 저장된 숫자 변환
		if (i == s.length() - 1)
		{
			int c = 1;
			a = 0;
			for (int k = t.size() - 1; k >= 0; k--)
			{
				a += (t[k] - '0') * c;
				c *= 10;
			}
			t.clear();
		}

		// - 면 빼고 -아니면 더함
		if (check)
		{
			sum -= a;
		}
		else
		{
			sum += a;
		}
		a = 0;

		// - 식별
		if (s[i] == '-')
		{
			check = 1;
		}
	}
	cout << sum;
	return 0;
}

반응형

예제 1

55-50+40

결과 1

예제 2

10+20+30+40

결과 2

예제 3

00009-00009

결과 3