문제 링크:
16637 괄호 추가하기 1
16638 괄호 추가하기 2
/* 1. 문제 잘못 읽음 : 괄호 안에는 하나의 연산자만 */
/* 2. 매 피연산자마다 선택지는 2개 : 이전 피연산자와 같은 괄호로 묶이거나 새 괄호로 묶이거나 -> 선택지 2개이므로 for문 사용 x */
/* 3. 첫번째 피연산자는 무조건 새 괄호로 묶임 : 선택지 없음 */
/* 4. ma, maximum answer를 answer의 최솟값 혹은 그 이하로 초기화하기 */
#include <iostream>
using namespace std;
int N; // 입력 문자열의 길이
int dgt[10]; int u[10]; // 피연산자의 배열, 피연산자가 속한 괄호 번호
int opn; char op[9]; // 연산자의 개수, 연산자의 배열
/* 4 */
long long pa, a, ma = -(1 << 31); // 일부 항의 연산 결과 partial answer, 모든 항의 연산 결과 answer, a들 중 최댓값 maximum answer
void calc(long long &a, char op, long long b) { // a = a (op) b
switch (op) {
case '+': a += b; break;
case '-': a -= b; break;
case '*': a *= b; break;
}
}
void calc_all() {
// 첫번째 항 또는 괄호 계산
a = dgt[0];
int opi = 0;
if (u[0] == u[1]) {
calc(a, op[0], dgt[1]);
opi = 1;
}
else opi = 0;
pa = dgt[opi + 1];
char opa = op[opi];
// 나머지 계산
for (opi = opi + 1; opi < opn; ++opi) {
if (u[opi] == u[opi + 1])
calc(pa, op[opi], dgt[opi + 1]);
else {
calc(a, opa, pa);
pa = dgt[opi + 1];
opa = op[opi];
}
}
calc(a, opa, pa);
if (a > ma)
ma = a;
}
void BF(int i, int un, bool up) {
if (i == opn + 1) {
calc_all();
return;
}
/* 2 */
if (!up) { /* 1 */
u[i] = un;
BF(i + 1, un, 1);
}
u[i] = un + 1;
BF(i + 1, un + 1, 0);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N; cin.get();
opn = (N + 1) / 2 - 1;
for (int i = 0; i < opn; ++i) {
dgt[i] = cin.get() - '0';
op[i] = cin.get();
}
dgt[opn] = cin.get() - '0';
u[0] = 0;
BF(1, 0, 0); /* 3 */
cout << ma;
return 0;
}/* 51분 소요 */
/* 1. list iterator */
#include <iostream>
#include <list>
using namespace std;
int N; // 입력 문자열의 길이
int dgt[10]; int u[10]; list<long long int> dgtv; // 피연산자의 배열, 피연산자가 속한 괄호 번호, 연산 후 잔여 피연산자의 리스트
int opn; char op[9]; list<char> opv; // 연산자의 개수, 연산자의 배열, 연산 후 잔여 연산자의 리스트
long long int pa, a, ma = -(1 << 31); // 일부 항의 연산 결과 partial answer, 모든 항의 연산 결과 answer, a들 중 최댓값 maximum answer
void calc(long long int &a, char op, long long int b) { // a = a (op) b
switch (op) {
case '+': a += b; break;
case '-': a -= b; break;
case '*': a *= b; break;
}
}
void calc_all() {
dgtv.clear();
opv.clear();
// 괄호 계산
pa = dgt[0];
for (int opi = 0; opi < opn; ++opi) {
if (u[opi] == u[opi + 1])
calc(pa, op[opi], dgt[opi + 1]);
else {
dgtv.push_back(pa);
pa = dgt[opi + 1];
opv.push_back(op[opi]);
}
}
dgtv.push_back(pa);
// * 계산
auto dgtit = dgtv.begin();
auto opit = opv.begin();
for (; opit != opv.end();)
if ((*opit) == '*') {
auto ndgtit = dgtit;
*dgtit = *dgtit * *(++ndgtit);
dgtv.erase(ndgtit); /* 1. ndgtit가 erase된 것이기 때문에 dgtit는 갱신할 필요 없음 */
opit = opv.erase(opit); /* 1. opit를 erase하고 다음 it를 opti에 할당 */
}
else {
++dgtit;
++opit;
}
// +, - 계산
dgtit = dgtv.begin();
a = *(dgtit++);
for (opit = opv.begin(); opit != opv.end(); ++dgtit, ++opit)
calc(a, *opit, *dgtit);
if (a > ma)
ma = a;
}
void BF(int i, int un, bool up) {
if (i == opn + 1) {
calc_all();
return;
}
if (!up) {
u[i] = un;
BF(i + 1, un, 1);
}
u[i] = un + 1;
BF(i + 1, un + 1, 0);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N; cin.get();
opn = (N + 1) / 2 - 1;
for (int i = 0; i < opn; ++i) {
dgt[i] = cin.get() - '0';
op[i] = cin.get();
}
dgt[opn] = cin.get() - '0';
u[0] = 0;
BF(1, 0, 0);
cout << ma;
return 0;
}#include <iostream>
#include <list>
using namespace std;
struct lmnt {
char op;
long long dgt;
int un;
};
int N, opn; // 입력 문자열의 길이
list<lmnt> org, cpy, prt;
long long pa, a, ma = -(1 << 31); // 일부 항의 연산 결과 partial answer, 모든 항의 연산 결과 answer, a들 중 최댓값 maximum answer
void calc(long long &a, char op, long long b) { // a = a (op) b
switch (op) {
case '+': a += b; break;
case '-': a -= b; break;
case '*': a *= b; break;
}
}
void calc_all() {
cpy = org;
for (int un = opn; un >= -opn; --un) {
for (auto cpy_it = cpy.begin(); cpy_it != cpy.end();){
if ((*cpy_it).un != un) { // 현재 괄호 번호에 해당하지 않으면 continue
++cpy_it;
continue;
}
auto prt_beg = cpy_it; // prt의 시작 위치 기록
prt.clear(); // prt 비우기
for (; cpy_it != cpy.end() && (*cpy_it).un == un; ++cpy_it) // prt 채우기 : 현재 괄호 번호에 해당하는 항들
prt.push_back(*cpy_it);
int prt_size = prt.size(); // prt 크기 기록
// * 계산
for (auto prt_it = prt.begin(); prt_it != prt.end();) {
auto prt_nit = prt_it;
if (++prt_nit == prt.end())
break;
if ((*prt_nit).op == '*') {
(*prt_it).dgt = (*prt_it).dgt * (*prt_nit).dgt;
prt.erase(prt_nit);
}
else
++prt_it;
}
// +, - 계산
auto prt_it = prt.begin();
a = (*prt_it).dgt;
for (++prt_it; prt_it != prt.end(); ++prt_it) {
calc(a, (*prt_it).op, (*prt_it).dgt);
}
// 항들 계산후 결과값을 시작항에 할당, 나머지 항들은 erase
(*prt_beg).dgt = a;
--(*prt_beg).un;
auto prt_begn = prt_beg;
++prt_begn;
while (--prt_size)
prt_begn = cpy.erase(prt_begn);
}
}
if (a > ma)
ma = a;
}
void BF(list<lmnt>::iterator it, int un) {
if (it == org.end()) {
calc_all();
return;
}
auto nit = it; ++nit;
(*it).un = un - 1;
BF(nit, un - 1);
(*it).un = un;
BF(nit, un);
(*it).un = un + 1;
BF(nit, un + 1);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N; cin.get();
org.push_back({ '\0', cin.get() - '0', 0 });
opn = (N + 1) / 2 - 1;
for (int i = 0; i < opn; ++i)
org.push_back({ (char)cin.get(), cin.get() - '0', 0 });
auto it = org.begin();
BF(++it, 0);
cout << ma;
return 0;
}우선순위는 피연산자가 아니라 연산자에 부여해야
특정 연산자의 양 이웃 중 적어도 하나와의 우선순위 차가 1이어야
