백준 14888 연산자 끼워넣기

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

 

서론

완전탐색 문제.

 

---

풀이

연산자를 끼워넣을 수 있는 모든 경우의 수를 만들기 위해 재귀를 이용한 완전탐색을 이용한다.

이를 위해 n-1개의 연산자 모두를 순서 상관없이 연산자 배열에 넣는다. 

그리고 재귀가 깊어질때마다 연산자를 하나씩 선택하고 선택된 연산자로 값을 연산한 후 연산된 값을 재귀로 계속 넘겨준다. 재귀가 끝에 다다르면 최대값과 최소값을 갱신한다.

void dfs(int idx, int opIdx, int sum){
    if(visited[opIdx] == 1) return; // 이미 선택된 연산자면 중복선택해선 안되므로 리턴
    else visited[opIdx] = 0;
    
    if(idx == n-1) { // n-1개의 연산자를 모두 선택했으면 최대, 최소 계산
    	resultMax = max(resultMax, sum);
        resultMin = min(resultMin, sum);
        return;
    }
    
    if(op[opIdx] == '+') sum += seq[idx]; // 연산자에 따라 sum을 갱신
    else if(op[opIdx] == '-') sum -= seq[idx];
    ...
    
    for(int i=0;i<n-1;i++){
    	dfs(idx+1, i, sum); // 완전탐색을 위한 재귀
    }
    
    visited[opIdx] = 0; // 최대 최소 계산이 끝난 연산자를 재사용하기 위해 중복체크해제
    return;
}

 

---

구현

// c++

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

using namespace std;

int resultMin = 0x7f7f7f7f;
int resultMax = -0x7f7f7f7f;
vector<pair<int, int>>op; // 0 : +, 1 : -, 2 : *, 3 : / 
vector<int>seq;
int n;

void init() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		seq.push_back(tmp);
	}
	for (int i = 0; i < 4; i++) {
		int tmp;
		cin >> tmp;
		while (tmp--) op.push_back({ i, 0 });
	}
}

void dfs(int idx, int opIdx, int sum) {
	if (idx != -1) {
		if (op[opIdx].second == 1) return;
		else op[opIdx].second = 1;

		if (op[opIdx].first == 0) sum += seq[idx + 1];
		else if (op[opIdx].first == 1) sum -= seq[idx + 1];
		else if (op[opIdx].first == 2) sum *= seq[idx + 1];
		else if (op[opIdx].first == 3) sum /= seq[idx + 1];
	}
	//cout << idx << endl;
	if (idx > n - 3) {
		resultMax = max(resultMax, sum);
		resultMin = min(resultMin, sum);
		op[opIdx].second = 0;
		return;
	}

	for (int i = 0; i < n - 1; i++) {
		dfs(idx + 1, i, sum); 
	}
	if(idx != -1) op[opIdx].second = 0;
	return;
}

int main() {
	init();
	dfs(-1, -1, seq[0]);
	cout << resultMax << endl << resultMin;
}