[BOJ] 14888번: 연산자 끼워넣기

문제 링크 : 백준/BOJ https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

아직도 재귀가 익숙치 않아서 완탐 문제를 가능한 재귀로 문제를 풀고자 노력 중이다.

주어진 N개의 배열에 대해 완탐을 어떻게 돌릴까 고민을 많이 했다.

재귀 함수를 짤 때, 탈출 조건 설정과 함께 인덱스 설정이 제일 어렵게 느껴진다.

그리고 알고리즘 헤더가 있는 것도 아니었는데, 백준 제출 시 변수명 min,max가 걸려서 컴파일 에러가 났다.

 

/*
14888번 - 연산자 끼워넣기
*/
#include <iostream>
#include <limits.h>
#include <vector>
using namespace std;

int n, minimum = INT_MAX, maximum = INT_MIN; int arr[12], sign[4];
void func(int res, int idx, int plus, int minus, int mul, int divide) {
	if (idx == n - 1) {
		if (res < minimum)
			minimum = res;
		if (res > maximum)
			maximum = res;
		return;
	}

	if (plus > 0) func(res + arr[idx + 1], idx + 1, plus - 1, minus, mul, divide);
	if (minus > 0)func(res - arr[idx + 1], idx + 1, plus, minus - 1, mul, divide);
	if (mul > 0)func(res*arr[idx + 1], idx + 1, plus, minus, mul - 1, divide);
	if (divide > 0)func(res / arr[idx + 1], idx + 1, plus, minus, mul, divide - 1);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int input;
		cin >> input;
		arr[i] = input;
	}

	for (int i = 0; i < 4; ++i) {
		int input;
		cin >> input;
		sign[i] = input;
	}

	func(arr[0], 0, sign[0], sign[1], sign[2], sign[3]);

	cout << maximum << "\n" << minimum;
}