백준 14888 - 연산자 끼워넣기

C++

14888 번 - 연산자 끼워넣기

문제

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오. 문제 출처

접근 방법

DFS를 이용하여 순열을 만드는 방법을 요구하는 문제이다. 입력 받은 연산자의 자리를 바꾸어 각 자리에 한번씩 위치하게 만들어 준다. 따라서 (n-1)! 만큼의 경우의 수가 나온다.

이후 각 경우의 수 연산자를 통해 결과를 구하고 그 결과의 최대, 최소를 구한다.

구현

각 수와 연산자를 입력을 받는다.

DFS로 순열을 구현한다. lv은 연산자를 뽑는 수라고 생각하며, n-1개의 연산자를 뽑으면 Cal 함수를 통해 계산을 한다. 한번 뽑은 연산자는 다시 뽑는 경우를 방지하기 위해 visited를 통해 구현한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int* arr;					//주어진 수를 넣는 배열
char operarr[10];			//새롭게 정렬 된 연산자 배열
vector<char> oper;			//초기에 연산자들을 저장하는 vector
bool visited[10];			//연산자 방문 여부를 따지는 bool 배열
vector<int> result;			//각 결과 값을 저장하는 vector

void DFS(int);
void Cal();

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;

	arr = new int[n];
	for (int i = 0; i < n; i++) {				//순열 입력
		cin >> arr[i];
		visited[i] = false;
	}

	int temp;
	char tempOper[4] = { '+', '-', '*', '/' };
	for (int i = 0; i < 4; i++) {
		cin >> temp;
		for (int j = 0; j < temp; j++) {
			oper.push_back(tempOper[i]);		//연산자 입력
		}
	}
	DFS(0);
	cout << *max_element(result.begin(), result.end()) << "\n";		//최댓값
	cout << *min_element(result.begin(), result.end());				//최솟값
	return 0;
}
//연산자 재정렬 - 순열
void DFS(int lv) {
	if (lv == n - 1) {
		Cal();
		return;
	}
	for(int i = 0; i < n - 1; i++) {
		if (!visited[i]) {
			operarr[lv] = oper[i];
			visited[i] = true;
			DFS(lv + 1);
			visited[i] = false;
		}
	}
}
//위치 된 연산자를 이용하여 계산을 한다.
void Cal() {
	int sum = arr[0];
	for (int i = 0; i < n - 1; i++) {
		char curStr = operarr[i];
		if (curStr == '+') {
			sum += arr[i + 1];
		}
		else if (curStr == '-') {
			sum -= arr[i + 1];
		}
		else if (curStr == '*') {
			sum *= arr[i + 1];
		}
		else if (curStr == '/') {
			sum /= arr[i + 1];
		}
	}
	result.push_back(sum);
}

후기 및 개선할 점

후기: 순열과 조합을 DFS로 편하게 구현할 수 있게 도와준 문제