백준 14888번 연산자 끼워넣기 C++ 백트래킹, 재귀

리뷰

숫자 사이에 연산자를 주어진 개수만큼 집어넣어 가장 큰 값과 작은 값을 구하는 문제 SWEA의 숫자 만들기와 동일한 문제

 

SWEA 4008번 [모의 SW 역량테스트] 숫자 만들기 C++ DFS, 백트래킹

 

 

문제 풀이

1. n값과 n개의 정수를 nums 배열에 입력 받아준다.
2. 덧셈, 뺄셈, 곱셉, 나눗셈의 각 연산자의 개수를 입력 받아준다.
3. 백트래킹을 시작한 후 내부에서 최소값과 최대값을 구해 최대값, 최솟값 순으로 줄바꿈하여 출력해 준다.

 

참고 사항

백트래킹 내부 구현

1. 기저 조건은 level이 n - 1에 달했을 때(모든 연산자를 소진했을 때)다.
2. 기저 조건에 달했을때 min_val 과 max_val값을 갱신해 주고 return 처리를 해준다.
3. 반복조건으로 연산자가 4개가 존재하니 0~4까지의 for문을 개행해 준다.
4. 판별식은 i번째 연산자가 존재하는지 판단해 준다.
5. 재귀 이전에는 i번째 연산자의 개수를 1개 줄여준다.
6. 재귀 시 level을 1 증가시켜 주고, 각 연산자에 맞는 연산을 val과 nums의 level + 1 인덱스를 진행해 준다.
7. 재귀 이후 줄여줬던 i번째 연산자의 개수를 다시 1개 늘려준다.
8. bt함수가 종료될때까지 해당 내용을 반복해 준다.

 

정답 코드

#include<iostream>

using namespace std;

int nums[100];
int op[4];
int n, min_val = 2e9, max_val = -2e9;

void bt(int level, int val) {
	if (level == n - 1) {
		min_val = min(min_val, val);
		max_val = max(max_val, val);
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (op[i]) {
			op[i]--;
			if (i == 0) bt(level + 1, val + nums[level + 1]);
			if (i == 1) bt(level + 1, val - nums[level + 1]);
			if (i == 2) bt(level + 1, val * nums[level + 1]);
			if (i == 3) bt(level + 1, val / nums[level + 1]);
			op[i]++;
		}
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> nums[i];
	cin >> op[0] >> op[1] >> op[2] >> op[3];
	bt(0, nums[0]);
	cout << max_val << "\n" << min_val << "\n";
}