백준 14888 (연산자 끼워넣기) C++

문제

14888번: 연산자 끼워넣기

수열을 입력 받고 그 사이에 연산자를 끼워 넣어 계산한 값이 가장 크게 되는 수와 가장 작게 되는 수를 출력하는 문제입니다.

 

숫자의 갯수는 N이라 할때 연산자의 갯수는 항상 N-1 개입니다. 

배열 arr는 수열의 수가 들어가는 배열입니다.

벡터 oper는 연산자가 들어가게 됩니다. 

덧셈은 0, 뺄셈은 1, 곱셈은 2, 나눗셈은 3이라고 할때

예를들어 n은 6이고 

덧뺄곱나 = 2 1 1 1 이라고 할떄 

oper 벡터에는 0 0 1 2 3 이 들어가게 됩니다. 

0이 두개, 1이 한개, 2가 한개, 3이 한개 이므로 일치합니다. 

vector<int> oper;
int arr[20];
int n;
int maxval = INT_MIN;
int minval = INT_MAX;
void calc();
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0, t; i < 4; i++) {
		cin >> t;
		while (t--)oper.push_back(i);
	}

	do {
		calc();
	} while (next_permutation(oper.begin(), oper.end()));

	printf("%d\n%d\n", maxval, minval);
	return 0;
}

next_purmutation 함수는 순열을 차례대로 배열해주는 함수입니다. 순열을 모두 배열하면 false를 출력하여 while문을

탈출하게 됩니다.  

void calc() {
	int res = arr[0];
	for (int i = 0; i < n - 1; i++) {
		if (oper[i] == 0) res += arr[i + 1];
		if (oper[i] == 1)res -= arr[i + 1];
		if (oper[i] == 2)res *= arr[i + 1];
		if (oper[i] == 3)res /= arr[i + 1];
	}
	if (res > maxval)maxval = res;
	if (res < minval)minval = res;
}

res의 값에 초기값 arr[0]을 설정해주고 oper[i]의 값에 따라 연산을 해주면 됩니다.

처음에 maxval은 가장 작은값, minval을 가장 큰 값을 미리 설정해주시고 진행하면 됩니다.

---

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
vector<int> oper;
int arr[20];
int n;
int maxval = INT_MIN;
int minval = INT_MAX;
void calc();
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0, t; i < 4; i++) {
		cin >> t;
		while (t--)oper.push_back(i);
	}

	do {
		calc();
	} while (next_permutation(oper.begin(), oper.end()));

	printf("%d\n%d\n", maxval, minval);
	return 0;
}
void calc() {
	int res = arr[0];
	for (int i = 0; i < n - 1; i++) {
		if (oper[i] == 0) res += arr[i + 1];
		if (oper[i] == 1)res -= arr[i + 1];
		if (oper[i] == 2)res *= arr[i + 1];
		if (oper[i] == 3)res /= arr[i + 1];
	}
	if (res > maxval)maxval = res;
	if (res < minval)minval = res;
}

전체 코드입니다.

---

방금 본 코드는 모든 후보군을 처음부터 끝까지 다 탐색한다는 단점이 있습니다.

이를 더욱 효율적으로 바꾸면 예를들어 덧셈 3개 뺄셈 1개 가 있다면 

1 + 2 + 3 + 4 - 5

1 + 2 + 3 - 4 + 5

1 + 2 + 3 까지는 같고 뒤에 두개의 연산자만 바꾸면 후보군을 조금더 효율적으로 확인해 볼 수 있습니다.

따라서 1 + 2 + 3 까지의 값을 저장하면 해결됩니다.

이는 재귀함수로 구현 가능합니다.

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int p, m, t, d;
	cin >> p >> m >> t >> d;
	recursion(1, p, m, t, d, arr[0]);
	printf("%d\n%d\n", maxval, minval);
	return 0;
}

변수 p는 덧셈의 갯수, m은 뺄셈의 갯수, t는 곱셈의 갯수, d는 나눗셈의 갯수입니다.

recursion함수는 (arr의 인덱스 번호, 덧셈의 갯수, 뺄셈의 갯수, 곱셈의 갯수, 나눗셈의 갯수, 지금까지 계산한 저장값)

입니다.

void recursion(int idx, int p, int m, int t, int d, int result) {
	if (idx == n) {
		if (result < minval)minval = result;
		if (result > maxval)maxval = result;
		return;
	}
	if (p > 0) recursion(idx + 1, p - 1, m, t, d, result + arr[idx]);
	if (m > 0) recursion(idx + 1, p, m - 1, t, d, result - arr[idx]);
	if (t > 0) recursion(idx + 1, p, m, t - 1, d, result * arr[idx]);
	if (d > 0) recursion(idx + 1, p, m, t, d - 1, result / arr[idx]);
}

idx는 arr의 인덱스 번호이므로 n이 되면 재귀함수를 멈추게 됩니다.

---

전체코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[20];
int n;
int maxval = INT_MIN;
int minval = INT_MAX;
void recursion(int idx, int p, int m, int t, int d, int result);
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	int p, m, t, d;
	cin >> p >> m >> t >> d;
	recursion(1, p, m, t, d, arr[0]);
	printf("%d\n%d\n", maxval, minval);
	return 0;
}
void recursion(int idx, int p, int m, int t, int d, int result) {
	if (idx == n) {
		if (result < minval)minval = result;
		if (result > maxval)maxval = result;
		return;
	}
	if (p > 0) recursion(idx + 1, p - 1, m, t, d, result + arr[idx]);
	if (m > 0) recursion(idx + 1, p, m - 1, t, d, result - arr[idx]);
	if (t > 0) recursion(idx + 1, p, m, t - 1, d, result * arr[idx]);
	if (d > 0) recursion(idx + 1, p, m, t, d - 1, result / arr[idx]);
}