[재귀] 14888 연산자 끼워넣기

연산자 끼워넣기 (boj.kr/14888)

 

문제 해설 및 주의사항

1. 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다

2. 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.

3. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

해설

---

적용한 레시피 / 방법론 + 접근법

1

풀이

1. 브루트 포스가 가능한가?

- N 이 11개, 연산자가 10개 가 최대이다. 그러므로, 10! 개. 브루트 포스가 가능한 경우의 수이다.

 

2. 필요한 파라미터들

- index : 현재 index ( 처음 값은 처음 호출 시 sum 에 들어가기 때문에, 1부터 시작 n 에서 종료 )

- sum : 현재 까지의 합

- plus, minus, mul, div : 각 연산자의 남은 횟수

3. 함수 구현

- 함수의 파라미터 index 가 하나씩 증가하면서, 연산자를 하나씩 넣어본다.

풀이코드

#include <iostream>
#include <algorithm>
using namespace std;
// 14888 연산자 끼워넣기

int n;
int A[12];

pair<int, int> solve(int index, int sum, int plus, int minus, int mul, int div){
	// 기저사례 : index 가 끝에 도달하면 return
	if(index == n){
		return make_pair(sum, sum);
	}
	
	vector<pair<int, int>> ret;
	
	if(plus > 0){
		ret.push_back( solve(index + 1, sum + A[index], plus - 1, minus, mul, div) );
	}
	if(minus > 0){
		ret.push_back( solve(index + 1, sum - A[index], plus, minus - 1, mul, div) );
	}
	if(mul > 0){
		ret.push_back( solve(index + 1, sum * A[index], plus, minus, mul-1, div) );
	}
	if(div > 0){
		ret.push_back( solve(index + 1, sum / A[index], plus, minus, mul, div - 1) );
	}
	
	auto ans = ret[0];
	for(auto p : ret){
		ans.first = ans.first < p.first ? p.first : ans.first;
		ans.second = ans.second > p.second ? p.second : ans.second;
	}
	
	return ans;
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++) cin >> A[i];
	
	int plus, minus, mul, div;
	cin >> plus >> minus >> mul >> div;
	
	pair<int, int> ans = solve(1, A[0], plus, minus, mul, div);
	printf("%d\n%d\n", ans.first, ans.second);
}

 

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점