[백준 C++] 14888번: 연산자 끼워넣기

1. 문제

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

2. 알고리즘 분류

• 브루트포스 알고리즘
• 백트래킹

 

3. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_N 11

using namespace std;

int N;
int max_val = -1000000000;
int min_val = 1000000000;
int numbers[MAX_N];
int num_operator[4];


void dfs(int cur, int res)
{
	// 모두 연산했을 경우
	if (cur == N - 1) {
		max_val = max(max_val, res);
		min_val = min(min_val, res);
		return;
	}

	// 모든 연산 탐색
	// i : 연산자 인덱스 (0 : 더하기, 1 : 빼기, 2 : 곱하기, 3 : 나누기)
	for (int i = 0; i < 4; i++) {
		if (num_operator[i] == 0) continue;

		int next = cur + 1;
		num_operator[i]--;

		if (i == 0)
			dfs(next, res + numbers[next]);
		else if (i == 1)
			dfs(next, res - numbers[next]);
		else if (i == 2)
			dfs(next, res * numbers[next]);
		else if (i == 3)
			dfs(next, res / numbers[next]);

		num_operator[i]++;
	}
}

int main() 
{
	// I/O 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	// N : 수의 개수 입력
	cin >> N;

	// 수 입력
	for (int i = 0; i < N; i++)
		cin >> numbers[i];

	// 연산 수 입력
	for (int i = 0; i < 4; i++)
		cin >> num_operator[i];

	// DFS 알고리즘
	dfs(0, numbers[0]);

	// 정답 출력
	cout << max_val << '\n' << min_val;
}

 

4. 유용한 알고리즘

1) DFS (깊이 우선 탐색) 알고리즘

void dfs(int cur, int res)
{
	// 모두 연산했을 경우
	if (cur == N - 1) {
		max_val = max(max_val, res);
		min_val = min(min_val, res);
		return;
	}

	// 모든 연산 탐색
	// i : 연산자 인덱스 (0 : 더하기, 1 : 빼기, 2 : 곱하기, 3 : 나누기)
	for (int i = 0; i < 4; i++) {
		if (num_operator[i] == 0) continue;

		int next = cur + 1;
		num_operator[i]--;

		if (i == 0)
			dfs(next, res + numbers[next]);
		else if (i == 1)
			dfs(next, res - numbers[next]);
		else if (i == 2)
			dfs(next, res * numbers[next]);
		else if (i == 3)
			dfs(next, res / numbers[next]);

		num_operator[i]++;
	}
}