<Baekjoon> #14888 DFS_연산자 끼워넣기 c++

#14888 연산자 끼워넣기

삼성 코딩테스트 기출 문제라고 한다

숫자들이 주어지고 그 사이에 적절하게 연산자를 끼워넣어서 최댓값과 최솟값을 구해야 한다. 주어진 연산자를 모두 다 썼을 때의 sum을 maxSum, minSum 과 비교해서 최댓값, 최솟값을 구해준다.

e.g. num={1,2,3,4,5,6}, (+)2개, (-)1개, (x)1개, (÷)1개인 경우
1 ⓐ 2 ⓑ 3 ⓒ 4 ⓓ 5 ⓔ 6 에서 각 ⓐⓑⓒⓓⓔ에 각 연산자를 적절하게 넣어야 한다.

이 과정을 연산자의 수 (n-1)만큼 반복해준다

1. 연산자 저장
   int op[4]에 각각의 연산자를 저장 (+,-,*,÷ 순서대로 개수를 저장)

	for (int i = 0; i < opNum; i++)
		cin >> op[i];

2. dfs 함수의 매개변수는 파라미터로는 int depth, int sum을 둔다

• depth는 +,- 등의 연산자를 몇 번째까지 채웠는지, 마지막까지 채웠을 때는 sum을 maxSum과 minSum을 비교한 후 return 하기 위함이다

void dfs(int depth, int sum) {
	if (depth == n - 1) {
		maxSum = max(maxSum, sum);
		minSum = min(minSum, sum);
		return;
	}
  ....
}

3. 연산자 사용
   op[i]에 저장된 연산자를 사용하기 위해 op[i]>0이면 op를 하나 사용하겠다는 의미로 op[i]--를 해주고 i값에 따라 +,-,*,/연산을 수행한 후 다시 사용할 것이므로 op[i]++를 해준다.
   (이 부분이 backtracking에서 가장 중요한 부분, 보통 다른 DFS를 이용한 backtracking에서는 visited[i]=true 로 바꾸었다가 visited[i]=false 로 바꾸는 게 많다)

	for (int i = 0; i < opNum; i++) {
		if (op[i]==0) continue;
		op[i]--;
		switch (i) {
		case 0: dfs(depth + 1, sum + num[depth + 1]); break;
		case 1: dfs(depth + 1, sum - num[depth + 1]); break;
		case 2: dfs(depth + 1, sum * num[depth + 1]); break;
		case 3: dfs(depth + 1, sum / num[depth + 1]); break;
		}
		op[i]++;
	}

전체코드

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

using namespace std;
const int opNum = 4;
int n;
vector<int> num;
int op[opNum];
int maxSum =-1000000000;
int minSum = 1000000000;

void dfs(int depth, int sum) {
	if (depth == n - 1) {
		maxSum = max(maxSum, sum);
		minSum = min(minSum, sum);
		return;
	}
	for (int i = 0; i < opNum; i++) {
		if (op[i]==0) continue;
		op[i]--;
		switch (i) {
		case 0: dfs(depth + 1, sum + num[depth + 1]); break;
		case 1: dfs(depth + 1, sum - num[depth + 1]); break;
		case 2: dfs(depth + 1, sum * num[depth + 1]); break;
		case 3: dfs(depth + 1, sum / num[depth + 1]); break;
		}
		op[i]++;
	}
}
int main() {
	cin >> n;
	num = vector<int>(n);
	for (int i = 0; i < n; i++)
		cin >> num[i];
	for (int i = 0; i < opNum; i++)
		cin >> op[i];
	dfs(0, num[0]);
	cout << maxSum << "\n" << minSum << endl;
	return 0;
}