[백준] 14888번 연산자 끼워넣기

입력 받은 연산자들을 사용하여 중복을 허용하지 않는 순열을 구현하면 된다. 연산자들 중 같은 연산자들이 여러 번 나오는 경우가 있기 때문에 해당 경우를 고려해야 한다.

 

 

tmp는 연산자들을 조합한 경우의 수를 뜻하고 oper_count는 0번째 자리는 + 갯수, 1번째 자리는 - 갯수, 2번째 자리는 * 갯수, 3번째 자리는 / 갯수를 뜻한다.

예를 들어, 예제 2번이 입력으로 주어지면 oper_count에는 [1, 0, 1, 0]이 들어가고 tmp는 [0, 2] 와 [2, 0] 이렇게 2가지 경우가 들어간다. (0은 +, 1은 -, 2는 *, 3은 / 를 뜻한다)

 

 

값들을 입력하고 함수를 호출한다.

 

 

중복 연산자는 갯수를 활용하여 처리했다. i는 연산자의 종류로 0은 +, 1은 -, 2는 *, 3은 / 를 뜻한다. oper_count에서 해당 연산자의 갯수를 확인하고 0보다 클 경우 tmp에 넣고 해당 연산자의 갯수를 1 빼주고 depth를 1 더해 함수를 다시 호출한다. 함수가 끝났을 경우 해당 연산자는 사용되고 다시 돌아왔으므로 1 더해준다.

depth == N-1이면 모든 연산자를 사용했으므로 계산을 한 후 answer 벡터에 추가한다.

 

 

모든 경우의 수를 넣은 뒤 sort 함수를 통해 오름차순으로 정렬 후 출력한다.

 

 

전체코드

#include <bits/stdc++.h>

using namespace std;

vector<int> numbers;	// 입력 받은 숫자 저장 배열
vector<int> tmp(101);	// 연산자 저장 배열
vector<int> oper_count;	// 연산자 갯수 [0] : + 갯수 , [1] : - 갯수 , [2] : * 갯수 , [3] : / 갯수
vector<int> answer;	// 계산값 저장 배열
int N;

void func(int depth) {
	// tmp 벡터에 저장된 연산자 갯수가 N-1일 때
	if (depth == N - 1) {
		int sum = numbers[0];
		for (int i = 0; i < N - 1; i++) {
			switch (tmp[i]) {
			case 0: {
				sum += numbers[i + 1];
				break;
			}
			case 1: {
				sum -= numbers[i + 1];
				break;
			}
			case 2: {
				sum *= numbers[i + 1];
				break;
			}
			default: {
				sum /= numbers[i + 1];
			}
			}
		}
		answer.push_back(sum);
		return;
	}

	for (int i = 0; i < 4; i++) {
		// 해당 연산자의 갯수가 남아있을 경우
		if (oper_count[i] > 0) {
			tmp[depth] = i;
			oper_count[i]--;
			func(depth + 1);
			oper_count[i]++;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		numbers.push_back(num);
	}

	for (int i = 0; i < 4; i++) {
		int num;
		cin >> num;
		oper_count.push_back(num);
	}
	
	func(0);

	sort(answer.begin(), answer.end());
	cout << *prev(answer.end()) << '\n';
	cout << *answer.begin();

	return 0;
}