15659(연산자 끼워넣기(3))
#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <iostream>
#include <stack>
#include <unordered_set>
#include <math.h>
using namespace std;
int N;
int A[11] = { 0 };
int O[4] = { 0 };// + - * /
int max_answer = -2147483647;
int min_answer = 2147483647;
vector<int> A_2;
vector<int> O_2;
vector<int> v;
int main(void)
{
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
freopen("input.txt", "r", stdin);
cin >> N;
for (int i = 0; i < N; i++)
cin >> A[i];
for (int i = 0; i < 4; i++)
cin >> O[i];
for (int i = 0; i < 4; i++)
for (int j = 0; j < O[i]; j++)
v.push_back(i);
do {
A_2.clear();
O_2.clear();
int temp = 0;
int flag = 0; // 곱셈 덧셈 플래그
int i = 0;
temp = A[0];
while (i < N - 1)
{
if (!flag)
temp = A[i];
if (v[i] < 2)
{
if (flag)
A_2.push_back(temp);
else
A_2.push_back(A[i]);
O_2.push_back(v[i]);
flag = 0;
}
else
{
if (v[i] == 2)
temp *= A[i + 1];
else
temp /= A[i + 1];
flag = 1;
}
i++;
}
if (v[N - 2] < 2)
{
A_2.push_back(A[N-1]);
}
else
{
A_2.push_back(temp);
}
int answer = A_2[0];
for (int i = 0; i < O_2.size(); i++)
{
if (O_2[i] == 0) // 연산자가 +이면
answer += A_2[i + 1];
else if (O_2[i] == 1) // 연산자가 -이면
answer -= A_2[i + 1];
}
max_answer = max(max_answer, answer);
min_answer = min(min_answer, answer);
} while (next_permutation(v.begin(), v.end()));
cout << max_answer << "\n" << min_answer;
}
고찰
문제는 간단하다 숫자 사이에 +, -, * ,/를 끼워넣어 최댓값 최솟값을 구하는것이다. 하지만 연산자 우선순위를 두어 *, /이 +, - 보다 연산되도록 한다. 우선 next_permutation으로 모든 조합의 연산자 순서를 정하고, *와 /를 먼저 계산하여 남은 연산자와, 새롭게 계산된 숫자를 새로운 각각 새로운 벡터에 넣는다. 그리고 남은 +,-를 계산하여 구현하였다. 생각보다 시간복잡도는 오래 걸리지 않았다, 하지만 구현과정이 까다로웠다. 특히 연산자 우선순위를 넣는부분에서 시간이 오래 걸렸다.