[백준 14888] 연산자 끼워넣기 (C++) - S1

문제

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

14888번: 연산자 끼워넣기

 

개요

문제를 읽자마자 백트래킹을 사용해야하겠다고 생각했다.

그러나, 백트래킹 문제를 안 풀어본지 너무 오래 되어서 함수를 어떻게 짜야 할지 뇌정지가 왔다.

그래서 결국 뇌정지를 이겨내지 못하고 구글링을 했다. (이 때 좀 현타가 세게 왔다.)

 

문제 풀이

전형적인 백트래킹 문제이다.

 

먼저, 수열과 연산자를 각각 배열에 저장한다.

그리고 백트래킹을 위한 함수 func를 main 함수 밖에 새롭게 작성해주어야 한다.

함수의 인자는 idx, result 2개이다.

idx는 수열에서 연산이 수행되는 숫자의 인덱스를 가리키고, result는 연산 후의 결과값을 저장하고 있다.

 

함수 내에서 4개의 if 문을 통해 덧셈, 뺄셈, 곱셈, 나눗셈의 경우를 나누어준다. 

해당 연산을 진행하게 되면 op 배열에서의 값을 1 줄여준다. ex) op[0]-- (덧셈 연산 진행)

if문 안에서 func 함수의 인자로 idx + 1과 result 뒤에 v[idx]에 대해 각각의 연산을 진행한 값을 넣어준다.

ex) func(idx + 1, result + v[idx])

if문 내의 func 함수가 종료되어 탈출하면 해당 연산의 op 배열에서의 값을 1 늘려준다. ex) op[0]++

그러면, 해당 연산의 if문을 탈출하여 다른 연산의 if문으로 들어가게 된다.

 

탈출 조건은 수열의 인덱스를 가리키는 idx의 값이 n이 될 때이다.

(수열의 마지막 값의 인덱스는 n - 1이고, 이 상태에서 연산 진행 후 idx + 1이 수행되면, 새로운 func 함수 내의 idx 값은 n이 된다)

식의 중간 결과값과 최종 결과값은 항상 -10억 이상, 10억 이하라고 주어져 있으므로 초기에 maxres는 -10억보다 1작은 -1000000001, minres는 10억보다 1 큰 1000000001으로 초기화해준다.

왜냐하면 maxres는 max 함수를 사용하는데, 맨 처음에 maxres 값에 어떤 값이 할당되기 위해서는 기존의 maxres에는 가능한 가장 작은 값을 가지고 있어야 한다. minres 또한 비슷하게 가능한 가장 큰 값을 처음에 가지고 있어야 한다.

 

코드

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

using namespace std;

int n;
int maxres = -1000000001, minres = 1000000001;
vector<int> v; // 수열
vector<int> op(4); // 연산자 (+, -, *, /)

void func(int idx, int result) {
	// 탈출 조건
	if (idx == n) {
		maxres = max(maxres, result);
		minres = min(minres, result);
	}

	// 덧셈
	if (op[0] > 0) {
		op[0]--;
		func(idx + 1, result + v[idx]);
		op[0]++;
	}
	// 뺄셈
	if (op[1] > 0) {
		op[1]--;
		func(idx + 1, result - v[idx]);
		op[1]++;
	}
	// 곱셈
	if (op[2] > 0) {
		op[2]--;
		func(idx + 1, result * v[idx]);
		op[2]++;
	}
	// 나눗셈
	if (op[3] > 0) {
		op[3]--;
		func(idx + 1, result / v[idx]);
		op[3]++;
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		v.push_back(num);
	}

	for (int i = 0; i < 4; i++) {
		cin >> op[i];
	}
	
	func(1, v[0]);
	cout << maxres << '\n' << minres;
	return 0;
}

 

중복된 코드를 제거하고, 더 간단한 형태로 작성한 코드는 다음과 같다.

#include <iostream>
#include <cstring>
#include <sstream>
#include <vector>
#include <deque>
#include <queue>
#include <map>
#include <algorithm>
#include <bitset>
#include <cmath>

using namespace std;

int n;
int maxres = -1000000001, minres = 1000000001;
vector<int> v; // 수열
vector<int> op(4); // 연산자 (+, -, *, /)

void func(int idx, int result) {
	if (idx == n) {
		maxres = max(maxres, result);
		minres = min(minres, result);
	}

	for (int i = 0; i < 4; i++) {
		if (op[i] > 0) {
			op[i]--;
			if (i == 0) func(idx + 1, result + v[idx]);
			if (i == 1) func(idx + 1, result - v[idx]);
			if (i == 2) func(idx + 1, result * v[idx]);
			if (i == 3) func(idx + 1, result / v[idx]);
			op[i]++;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		v.push_back(num);
	}

	for (int i = 0; i < 4; i++) {
		cin >> op[i];
	}
	
	func(1, v[0]);
	cout << maxres << '\n' << minres;
	return 0;
}

 

깨달은 점

백트래킹 문제를 너무 오랜만에 마주해서 뇌정지가 왔었다.

스스로도 백트래킹 문제에 약하다는 것을 인지하고 있었는데, 이 정도까지 뇌정지가 올 줄은 몰랐다.

꾸준히 이 유형을 풀어보는 것이 답일 것 같다.