[BOJ] 16637: 괄호 추가하기

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

16637번: 괄호 추가하기

 

문제만 보면 복잡해 보이지만, 문제에 다음과 같은 제약 조건이 있기 때문에 생각보다 간단하게 구현할 수 있다.

 

1. 연산자의 우선순위는 모두 동일하다.

2. 괄호 안에는 연산자가 하나만 들어 있어야 한다.

3. 중첩된 괄호는 사용할 수 없다.

 

때문에 무조건 (2 + 3) * (3 + 2) + (2 - 3)이나 2 + 3 - 10 * (2 - 5)와 같은 형태가 될 것이다.

 

이러면 그냥 각각의 연산자마다 자신을 먼저 계산할지 말지만 정해주고 계산하면 된다.

 

어떻게 구현할 수 있을까?

8+3*5*2에서 3*5를 먼저 계산하고 싶다면,

8+(3*5)+0*2 와 같은 형태로 바꾸면 된다.

 

어차피 연산자 우선순위가 존재하지 않고, 중첩된 괄호는 사용할 수 없고, 괄호 안에는 연산자가 하나만 들어 있어야 하기 때문에 8 + 15 + 0 * 2던 8 + (3 * 5) + 0 * 2던 8 + (3 * 5) * 2던 결과가 똑같이 나온다.

 

그러면 이 방법으로는 0.5초의 시간 제한 안에 돌아갈 수 있을까?

 

한 자리 정수와 연산자가 번갈아가며 나오기 때문에 연산자의 개수는 M=(N-1)/2개, 최대 9개이고,

괄호를 중첩해 사용할 수 없는 것을 생각하지 않으면, 연산자마다 괄호를 추가한다, 괄호를 추가하지 않는다를 선택할 수 있다.

따라서 시간 복잡도는 O(2^M)으로 2^9 = 512이기 때문에 시간 안에 풀 수 있다.

 

먼저 구현을 최우선으로 생각하고 작성한 코드

#include <iostream>
#include <string>
#include <algorithm>

int N;
std::string str;
int val[20];

void set(int index, int val1, char oper, int val2) {
	val[index * 2] = val1;
	str[index * 2 + 1] = oper;
	val[index * 2 + 2] = val2;
}

int calculate() {
	int value = val[0];
	for (int i = 0; i < N / 2; ++i) {
		char oper = str[i * 2 + 1];
		int other = val[i * 2 + 2];
		value = (oper != '+') ? ((oper == '-') ? value - other : value * other) : value + other;
	}
	return value;
}

int solve(int index, bool bracketed) {
	if (index == N / 2) return calculate();

	// index + 1번째 연산자에 괄호를 추가하지 않는 경우
	int ret = solve(index + 1, false);
	if (bracketed) return ret;

	int val1 = str[index * 2] - '0';
	int val2 = str[index * 2 + 2] - '0';
	char oper = str[index * 2 + 1];

	int alterVal = (oper != '+') ? ((oper == '-') ? val1 - val2 : val1 * val2) : val1 + val2;
	set(index, alterVal, '+', 0);

	// index + 1번째 연산자에 괄호를 추가하는 경우와 비교해 최댓값 저장
	ret = std::max(ret, solve(index + 1, true));

	set(index, val1, oper, val2);

	return ret;
}

int main() {
	std::cin >> N >> str;
	for (int i = 0; i < N; i += 2) {
		val[i] = str[i] - '0';
	}
	std::cout << solve(0, false);

	return 0;
}

 

그리고 아래는 최백준씨의 코드인데, 이를 분석해 보았다.

 

struct Term {
    int num;
    int op;
};

 

정수일 경우에는 num에 값을 설정하고 op에 0을

연산자일 경우에는 num에 0을 설정하고 op에 1(+), 2(-), 3(*)으로 설정해 주는 방식이다.

 

for (int i=0; i<n; i++) {
        if (i%2 == 0) {
            a[i] = {s[i]-'0', 0};
        } 
        else {
            int op = 1;
            if (s[i] == '-') {
                op = 2;
            } 
            else if (s[i] == '*') {
                op = 3;
            }
            a[i] = {0, op};
        }
    }

 

가장 먼저 입력받은 문자열을 Term으로 바꾸어 주는 과정이다.

문제의 제약 조건으로 인해 수는 무조건 짝수 번째 인덱스, 연산자는 무조건 홀수 번째 인덱스를 가진다.

 

for (int i=0; i<(1<<m); i++) {
    bool ok = true;
    for (int j=0; j<m-1; j++) {
      if ((i&(1<<j)) > 0 && (i&(1<<(j+1))) > 0) {
          ok = false;
      }
    }
    if (!ok) continue;

    // ...
}

 

브루트포스로 가능한 모든 경우를 시도해 본다.

비트마스킹을 사용하고 있는데, i의 n번째 비트가 1이라면, n번째 연산자에는 괄호가 붙은 것이다.

 

중첩된 괄호를 사용할 수 없기 때문에, i의 j번째 비트와 j+1번째 연산자에 모두 괄호가 추가된 경우는 시도하지 않는다.

 

for (int j=0; j<m; j++) {
  if ((i&(1<<j)) > 0) {
    int k = 2*j+1;
    if (b[k].op == 1) {
      b[k-1].num += b[k+1].num;
      b[k+1].num = 0;
    } 
    else if (b[k].op == 2) {
      b[k-1].num -= b[k+1].num;
      b[k].op = 1;
      b[k+1].num = 0;
    } 
    else if (b[k].op == 3) {
      b[k-1].num *= b[k+1].num;
      b[k].op = 1;
      b[k+1].num = 0;
    }
  }
}

 

처음에 말한 것과 같이, 복사한 벡터 b에서 연산자의 왼쪽 수에 계산한 값을 집어넣고 오른쪽 수는 0으로 만든다.

연산자는 모두 + 또는 -로 만들면 되는데, +로 통일했다.

 

int res = b[0].num
for (int j=0; j<m; j++) {
  int k = 2*j+1;
  if (b[k].op == 1) {
    res += b[k+1].num;
  } 
  else if (b[k].op == 2) {
    res -= b[k+1].num;
  } 
  else if (b[k].op == 3) {
    res *= b[k+1].num;
  }
}
if (ans < res) {
  ans = res;
}

 

마지막으로 바꾼 식을 계산한 뒤, 최댓값을 갱신해주면 끝이다.

 

전체 코드

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Term {
    int num;
    int op;
};
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<Term> a(n);
    for (int i=0; i<n; i++) {
        if (i%2 == 0) {
            a[i] = {s[i]-'0', 0};
        } else {
            int op = 1;
            if (s[i] == '-') {
                op = 2;
            } else if (s[i] == '*') {
                op = 3;
            }
            a[i] = {0, op};
        }
    }
    int m = (n-1)/2;
    int ans = -2147483648;
    for (int i=0; i<(1<<m); i++) {
        bool ok = true;
        for (int j=0; j<m-1; j++) {
            if ((i&(1<<j)) > 0 && (i&(1<<(j+1))) > 0) {
                ok = false;
            }
        }
        if (!ok) continue;
        vector<Term> b(a);
        for (int j=0; j<m; j++) {
            if ((i&(1<<j)) > 0) {
                int k = 2*j+1;
                if (b[k].op == 1) {
                    b[k-1].num += b[k+1].num;
                    b[k+1].num = 0;
                } else if (b[k].op == 2) {
                    b[k-1].num -= b[k+1].num;
                    b[k].op = 1;
                    b[k+1].num = 0;
                } else if (b[k].op == 3) {
                    b[k-1].num *= b[k+1].num;
                    b[k].op = 1;
                    b[k+1].num = 0;
                }
            }
        }
        int res = b[0].num;
        for (int j=0; j<m; j++) {
            int k = 2*j+1;
            if (b[k].op == 1) {
                res += b[k+1].num;
            } else if (b[k].op == 2) {
                res -= b[k+1].num;
            } else if (b[k].op == 3) {
                res *= b[k+1].num;
            }
        }
        if (ans < res) {
            ans = res;
        }
    }
    cout << ans << '\n';
    return 0;
}