[백준 16637] 괄호 추가하기

문제 출처: https://www.acmicpc.net/problem/16637

풀이

1. 연산자갯수와 숫자의 갯수를 각각의 배열에 담는다.

길이가 최대 19이므로 연산자9개, 피연산자 10개까지 나올 수 있다. 피연산자의 개수는 index1, 연산자의 갯수는 index2가 된다. 

내 풀이는 연산자기준으로, 연산자를 모두쓰게되면 계산 종료후 최댓값을 갱신한다.

2. 괄호쳐서 계산하는 것 잘 이해하기(괄호 치는 것만으로

대충 괄호를 쳐서 계산하는것과 괄호를 치지않고 쭉 계산해나가는 식을 작성해야함은 알 수 있다.  

괄호를 안치고 계산하는 연산은 아래 코드처럼, 연산후, dfs를 계속 돌리면된다. 

//앞에서부터 계산하기
	int res = func(sum, num[cnt + 1],op[cnt]);
	//dfs돌려서 확인하기(더 계산할 수 있는지)
	dfs(res, cnt + 1);

괄호를 쳐서 계산하는연산을 보자. 

1+2*3 일 때 괄호를 치려면, 일단 연산자가 최소 2개는 있어야한다.( 1+2 꼴일때는 괄호치는것과 안치는것 결과값같음)

따라서 1+(2*3)꼴이 되게하려면 현재 사용되고있는 연산자+1 인덱스의 연산자가 존재할 때 계산해야한다.

즉, 현재 cnt=0이라 op[cnt]=='+'인데, 1+(2*3)처럼 괄호를 치려면, cnt+1(op[cnt+1]=='*')가 아직 사용되지않았을 때다.

그리고나서 2*3을 구한뒤(a), 1과 a를 더해주면 1+(2*3)을 계산하게된다. 괄호안치는 연산 1+2*3은 이미 위의 코드로 잘 계산되고있다.

주의할 것은 b(1+ (2*3)을 계산한 값)를 구하는 func함수의 인자 순서다.

1+(2*3)일 때, (2*3)+1가 아니라 1+(2*3)이다. 계산을 괄호식부터 할 뿐이다. 주의하자. 똑같은 얘기가 아니다.

즉, 순서를 주의해야한다.

예를들어 1-9-9일 때, func함수의 인자를 (sum,a)가 아닌 (a, sum)으로 바꾸면 1-(9-9)가 아닌 (9-9)-1가 되버려서 값이 달라져버린다.  

따라서, 인자는 sum뒤에 a가 나와야한다. (a뒤에 sum이 나오게되면안됨)

그리고, 잔실수 할수 있는 부분인데, func함수의 첫번째 인자는 num[cnt]이 아닌 sum이다.

1+(2*3)일 떄, 처음 계산할 때만 생각하면 sum=1이고 num[cnt]=1 이라 똑같은 값이라고 생각할 수 있는데, 그렇게되면 아래 식이 잘못된 값이 된다.

1+2*3+5*7일 떄를 보자.

만약 func의 첫번째 인자를 num[cnt]로 작성해버리면, 1+(2*3)=7까지 계산후 7+(5*7)이 아닌, 3+(5*7)이 된다. 즉, 누적된값을 유지해야한다.

위에서 길게 얘기한 것들을 코드로 작성하면된다.

코드

#include<iostream>
#include<string>
using namespace std;
int n;
string s;
int num[10],index1, index2, max_val = -100;
char op[10];
void dfs(int sum, int cnt);
int func(int a, int b, char c);
int main()
{
	cin.tie(0);
	cin.sync_with_stdio(false);
	cin >> n;
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		//숫자면 숫자배열에저장
		if (i % 2 == 0) {
			num[index1] = s[i] - '0';
			index1++;
		}
		else {
			op[index2] = s[i];
			index2++;
		}
	}
	dfs(num[0], 0);
	cout << max_val << '\n';
}
void dfs(int sum, int cnt)
{
	//모든 연산자를 사용하게됐을 때는 종료
	if (cnt == index2)
	{
		if (max_val < sum)
			max_val = sum;
		return;
	}
	//앞에서부터 계산하기
	int res = func(sum, num[cnt + 1],op[cnt]);
	//dfs돌려서 확인하기(더 계산할 수 있는지)
	dfs(res, cnt + 1);
	//괄호를 쳐서 계산하기
	//만약 계산할 연산자가 아직 남았으면 계산하기
	if (cnt + 1 < index2)
	{
		//1+2*3+5일 떄 1+(2*3)+5하는 과정
		int a = func(num[cnt + 1], num[cnt + 2], op[cnt + 1]);
		//조심!) func의 1,2번쨰 인자 순서바꾸면 틀림
		//조심!)func의 첫번째인자는 num[cnt]가 아님
		int b = func(sum, a, op[cnt]);
		//+5계산하기위해 2칸 건너뜀(+:0, *:1, +:2)
		dfs(b, cnt + 2);
	}
}
int func(int a, int b, char c)
{
	if (c == '+')return a + b;
	else if (c == '-')return a - b;
	else if (c == '*')return a * b;
	else
		exit(1);
}

결과