14888 연산자 끼워넣기 ( DFS : 중복순열 || next_permutation)

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

14888번: 연산자 끼워넣기

 

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std; 

// DFS
int n;
int arr[12];
vector <int> op;
bool visit[12];
int min_answer, max_answer;


vector <int> v;


// 연산자들 뽑기 
// 순열
void DFS(int pick) {

	// 모두 뽑았음
	if(pick == n-1) {
		// calculate
		int result = arr[0];
		for(int i=0; i<v.size(); i++) {
			int b = arr[i+1];
			int oper = v[i];

			if(oper == 0) {
				result += b;
			}
			else if (oper == 1) {
				result -= b;
			}
			else if (oper == 2) {
				result *= b;
			}
			else {
				result /= b;
			}
		}
		min_answer = min(min_answer, result);
		max_answer = max(max_answer, result);
		return;
		
	}

	for (int i=0; i<n-1; i++) {
		if(visit[i] == true) continue;

		visit[i] = true;
		v.push_back(op[i]);
		DFS(pick+1);
		visit[i] = false;
		v.pop_back();
	}

}

int main() {

	scanf("%d", &n);

	for(int i=0; i<n; i++)
		scanf("%d", &arr[i]);

	for(int i=0; i<4; i++) {
		int operate;
		scanf("%d", &operate);

		for(int j=0; j<operate; j++) {
			op.push_back(i);
		}
	}

	min_answer = 987654321;
	max_answer = -987654321;

	DFS(0);

	printf("%d\n%d\n", max_answer, min_answer);

	return 0;
}

 

1. 주어진 연산자 갯수에 따라 연산자값을 op 에 저장한다. 

ex ) 

6
1 2 3 4 5 6
2 1 1 1

일 경우,

idx 0 : + :2

idx 1 : - : 1

idx 2 : * : 1

idx 3:  / : 1

 임으로, op[5] = {0, 0, 1, 2, 3} 순으로 들어간다.

 

2. 디피를 돌면서 op 의 원소들의 순열을 구한다.

 

3. 돌고 난 후, 구한 연산자 순열으로 계산 결과를 구한다.

 

 

next_permutation

next_permutaion 으로 순열을 자동으로 구할 수 있다.

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std; 

// 순열
int n;
int arr[12];
vector <int> op;
int min_answer, max_answer;


int main() {


	min_answer = 987654321;
	max_answer = -987654321;

	scanf("%d", &n);

	for(int i=0; i<n; i++)
		scanf("%d", &arr[i]);

	for(int i=0; i<4; i++) {
		int operate;
		scanf("%d", &operate);

		for(int j=0; j<operate; j++) {
			op.push_back(i);
		}
	}

	sort(op.begin(), op.end());
	do {

		int result = arr[0];
		for(int i=0; i<op.size(); i++) {
			int b = arr[i+1];
			int oper = op[i];

			if(oper == 0) {
				result += b;
			}
			else if (oper == 1) {
				result -= b;
			}
			else if (oper == 2) {
				result *= b;
			}
			else {
				result /= b;
			}
		}
		min_answer = min(min_answer, result);
		max_answer = max(max_answer, result);


	}while(next_permutation(op.begin(), op.end()));


	printf("%d\n%d\n", max_answer, min_answer);

	return 0;
}