괄호 추가하기
문제 해석
주어진 수식에 적절히 괄호를 추가하여 식의 결과의 최댓값을 구하는 문제입니다.
괄호안에는 연산자가 하나만 들어있어야하고, 중첩된 괄호를 사용할 수 없습니다.
괄호안에 들어있는 식을 먼저 계산합니다.
연산자 우선순위는 동일하기 때문에, 수식을 계산할 때 왼쪽에서부터 순서대로 계산합니다.
설계(20)
괄호를 추가할 지 안할지 선택하여 연산을 수행한 뒤 최댓값을 갱신하는 완전탐색 문제입니다.
각 인덱스에 대해 숫자가 있는 부분이고 used가 0이면(괄호가 안채워져있으면) 괄호를 채워넣는 작업을 합니다.
괄호를 추가할지 체크하는 부분을 used배열을 이용합니다. used가 1이면 괄호가 시작하는 위치, 2이면 끝나는 위치로 표시해줍니다.
모든 위치를 탐색했으면, used 상태에 따라서 괄호를 배치해준 후, 괄호가 있는 부분을 먼저 계산해줍니다.
각 괄호의 결과값, 숫자, 연산자를 string형 벡터에 저장해줍니다.
이후, 왼쪽부터 순서대로 계산해줍니다.
주의해야할 점은 최댓값 ans의 초기값을 -2^31로 해주어야 합니다.
구현(40)
코드
#include <iostream>
#include <vector>
#include <string>
#include <limits.h>
#include <algorithm>
using namespace std;
#define INF INT_MAX
#define MAXN 20
int used[MAXN];
int ans = -INF;
string s;
int N;
int Op(int a, int b, char op) {
if (op == '+') return a + b;
else if (op == '-') return a - b;
return a * b;
}
void go(int now) {
if (now == s.length()) {
vector<string> vt;
for (int i = 0; i < s.length(); i++) {
if (used[i] == 1) {
vt.push_back(to_string(Op(s[i]-'0', s[i + 2]-'0', s[i + 1])));
i +=2;
}
else if (used[i] == 0) {
string tmp_s = "";
tmp_s = s[i];
vt.push_back(tmp_s);
}
}
int sum = stoi(vt[0]);
for (int i = 1; i < vt.size(); i+=2) {
sum = Op(sum, stoi(vt[i + 1]), vt[i][0]);
}
if (ans < sum) ans = sum;
return;
}
if (s[now] >= '0' && s[now] <= '9') {
if (!used[now] && now < s.length() - 1) {
used[now] = 1;
used[now + 2] = 2;
go(now + 3);
used[now] = 0;
used[now + 2] = 0;
}
go(now + 1);
}
else go(now + 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> s;
go(0);
cout << ans << "\n";
return 0;
}
디버깅
처음에 지문을 제대로 읽지 않아서 알고리즘 설계를 잘못하였습니다.
괄호안에 연산자가 하나만 있어야한다는 조건을 배제하고 설계하였습니다.
이 오류를 파악하고 다시 설계하였습니다.
제출결과
0 ms
마무리
생각보다 구현하는데 오래걸린 완전탐색문제였습니다.
int형과 char형을 복합적으로 벡터에 저장하기 어렵기 때문에 string형으로 변환해주는 작업이 필요했습니다.