14888번 연산자 끼워넣기

14888번: 연산자 끼워넣기

또또 브루트포스 문제이다. 

 

삼성역량테스트에는 브루트포스문제가 단골로 등장하나보다.

 

대부분의 브루트포스 문제는 N과M 시리즈를 참조할 수 있으니 브루트포스가 감이 잡히지 않는다면 꼭 다 풀어보자.

 

숫자와 그 사이에 끼워넣을 연산자가 입력으로 주어지면 

 

연산자 순서를 이리저리 바꾸면서 계산할 수 있는 값의 최대 최소를 구하면 된다.

 

이번 문제는 크게 두 부분으로 나누자면

 

1. 모든 경우의 연산자 조합을 만들기 (중복된 조합을 허용하지 않는다)

2. 주어진 연산자 순서로 계산하기

 

연산자에 관한 정보를 어떻게 저장할지에 대해 약간 고민이 필요하고

 

중복된 조합을 허용하지 않기 위해 set 라이브러리를 사용했다. (아니면 시간초과가 뜨지 않을까)

 

+ set iterator 순회와 열거형 사용에 익숙해져야겠다.

 

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

enum Op { PLUS, MINUS, MULTI, DIV };

vector<pair<int, bool>> check_op;
vector<int> vec;
vector<int> result;
int vec_temp[11];
int num[11];
set<vector<int>> s;
int N, op_num;
int op[4];

void print() {
	cout << '\n';
	/*
	for (int i = 0; i < check_op.size(); i++) {
		cout << check_op[i].first << " ";
	}
	*/
	/*
	for (int i = 0; i < op_num; i++) {
		cout << vec_temp[i] << " ";
	}
	*/
	set<vector<int>>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		const vector<int>&i = (*iter);
		for (int j = 0; j < i.size(); j++) {
			cout << i[j] << " ";
		}
		cout << '\n';
	}
	cout << '\n';
}

void cal() {
	set<vector<int>>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		const vector<int>&i = (*iter);
		int z = num[0];
		for (int j = 1; j <= i.size(); j++) {
			switch (i[j-1]) {
			case PLUS:
				z = z + num[j]; break;
			case MINUS:
				z = z - num[j]; break;
			case MULTI:
				z = z * num[j]; break;
			case DIV:
				z = z / num[j]; break;
			}
		}
		result.push_back(z);
	}
}

void func(int cnt) {
	if (cnt == op_num) {
		vec.clear();
		for (int i = 0; i < op_num; i++) {
			vec.push_back(vec_temp[i]);
		}
		s.insert(vec);
		return;
	}
	for (int i = 0; i < op_num; i++) {
		if (!check_op[i].second) {
			vec_temp[cnt] = check_op[i].first;
			check_op[i].second = true;
			func(cnt + 1);
			check_op[i].second = false;
		}
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;
		num[i]=temp;
	}
	for (int i = 0; i < 4; i++) {
		cin >> op[i];
	}

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < op[i]; j++) {
			switch (i) {
			case PLUS:
				check_op.push_back(pair<int,bool>(PLUS, false)); op_num++;
				break;
			case MINUS:
				check_op.push_back(pair<int, bool>(MINUS, false)); op_num++;
				break;
			case MULTI:
				check_op.push_back(pair<int, bool>(MULTI, false)); op_num++;
				break;
			case DIV:
				check_op.push_back(pair<int, bool>(DIV, false)); op_num++;
				break;
			}
		}
	}
	func(0);
	//print();
	cal();
	sort(result.begin(), result.end());
	cout << result.back() << '\n' << result.front();
	return 0;
}

 

 

스무스하게 1트 클리어

 

 

15665번: N과 M (11)