BOJ - 14888번 연산자 끼어넣기(C++)

문제 출처 : https://www.acmicpc.net/problem/14888

문제 난이도

Sliver 1

접근법

dfs를 이용한 백 트래킹

코드

#include <iostream>

using namespace std;

int num[11];
int minV = 987654321, maxV = -987654321;
int N;

void dfs(int index, int plus, int minus, int multi, int div, int sum) {
	if (index == N) {
		if (minV > sum) minV = sum;
		if (maxV < sum) maxV = sum;
		return;
	}

	if (plus > 0) {
		dfs(index + 1, plus - 1, minus, multi, div, sum + num[index]);
	}
	if (minus > 0) {
		dfs(index + 1, plus, minus-1, multi, div, sum - num[index]);
	}
	if (multi > 0) {
		dfs(index + 1, plus, minus, multi-1, div, sum *num[index]);
	}
	if (div > 0) {
		dfs(index + 1, plus, minus, multi, div-1, sum / num[index]);
	}	
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int plus, minus, multi, div;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	cin >> plus >> minus >> multi >> div;
	dfs(1, plus, minus, multi, div, num[0]);
	cout << maxV << "\n";
	cout << minV << "\n";
	return 0;
}

피드백

처음에 틀렸는데 이유가 maxVal 초기값을 -1이라고 해서 그렇다. 문제에서 조건이 중간에서 값이 -10억이 나올 수 있다고 했기에 maxVal은 -1이 된다. 그래서 10억보다 큰 초기값을 지정했더니 통과했다.