[재귀] 연산자 끼워넣기 (2) 15658

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

 

문제 해설 및 주의사항

1.연산자 끼워넣기와 비슷하다.

2. 달라진 점은, 연산자의 개수가 딱 맞게 떨어지지는 않는다는 점이다.

해설

---

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

 

풀이

1. 위의 이전문제와 풀이는 아예 동일하다.

2. 재귀함수의 기저사례가 연산자의 개수와는 관계없기 때문이다.

풀이코드

#include <iostream>
#include <algorithm>
using namespace std;
// 15658 연산자 끼워넣기 (2)

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);
}

 

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