[baekjoon 14888] 연산자 끼워넣기(브루트포스, 백트래킹) (C++)

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

14888번: 연산자 끼워넣기

 

연산자가 주어지고, 해당 연산자들을 이용해서 만들 수 있는 최댓값과 최솟값을 구하는 문제다.

어느 연산자를 배치해서 최댓값이 나올 것이고, 최솟값이 나올 것이고 계산을 하긴 힘들다.

그리고 N의 개수는 최대 11이고 연산자의 개수는 최대 10개이므로 모든 경우의 수를 돌려서 찾아야 하는 문제이다.

 

1. DFS + 백트래킹을 이용해서 모든 경우의 수를 찾을 수 있다.

만약 연산자 +, -, *, / 가 1 0 1 0 이면 for문을 돌면서 연산자 개수가 >0 이상인 것을 찾아 들어가면서 끝나고 백트래킹으로 증가시켜주면 모든 경우의 수를 찾을 수 있다.

 

2. 나는 모든 경우의 수를 다 찾되, 순열을 이용했다.

 

1 2 0 1개가 있으면, 1 2 2 4를 갖고 만들 수 있는 모든 경우의 수를 순열로 만드는 것이다.

1 2 2 4

1 2 4 2

1 4 2 2

2 1 2 4

2 2 1 4

... 이렇게 늘어날 것이고, 해당 case마다 숫자를 계산해서 최댓값, 최솟값을 갱신해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1000000000
#define MIN -1000000000

using namespace std;

int n, x, maxA = MIN, minA = MAX;
vector<int> numList, opList, operation;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		numList.push_back(x);
	}

	for (int i = 0; i < 4; i++) {
		cin >> x;
		opList.push_back(x);
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < opList[i]; j++) {
			operation.push_back(i);
		}
	} // 연산자 개수대로 펼치기

	do {
		int temp = numList[0];
		for (int i = 0; i < operation.size(); i++) {
			if (operation[i] == 0) {
				temp += numList[i + 1];
			}
			else if (operation[i] == 1) {
				temp -= numList[i + 1];
			}
			else if (operation[i] == 2) {
				temp *= numList[i + 1];
			}
			else {
				temp /= numList[i + 1];
			}
		}
		maxA = max(temp, maxA);
		minA = min(temp, minA);
		
	} while (next_permutation(operation.begin(), operation.end()));

	cout << maxA << "\n" << minA;
}

c++의 next_permutation을 이용해서 손쉽게 풀었다.