BaekJoon 14888번: 연산자 끼워넣기

풀이법

1) 재귀 함수를 이용하여 level에 도달하게 되면 출력하는 형식으로 BackTracking을 구현한다.

2) 재귀의 흐름과 매개변수를 잘 고르는 것이 중요하다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define INF 1000000001
using namespace std;

int n;
vector<int> vec;
int arith[4];
int visit[4];
int maxVal = -INF;
int minVal = INF;
void backtrack(int temp,int level)
{
	if (level == n)
	{
		if (temp > maxVal)
		{
			maxVal=temp;

		}
		if (temp < minVal)
		{
			minVal = temp;
		}
		return;
	}

	for (int j = 0; j < 4; j++)
	{
		if (arith[j] == 0)
		{
			continue;
		}
		if (arith[j] <= visit[j])
		{
			continue;
		}
		visit[j]++;
		if (j == 0)
		{
			backtrack(temp + vec[level] , level + 1);
		}
		else if (j == 1)
		{
			backtrack( temp - vec[level] , level + 1);
		}
		else if (j == 2)
		{
			backtrack(temp * vec[level], level + 1);

		}
		else if (j == 3)
		{
			backtrack(temp / vec[level], level + 1);
		}
		visit[j]--;
	}
	

}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		vec.push_back(a);
	}
	for (int i = 0; i < 4; i++)
	{
		int a;
		cin >> a;
		arith[i] = a;
	}
	memset(visit, 0, sizeof(visit));
	backtrack(vec[0],1);
	cout << maxVal<<"\n";
	cout << minVal;
}

3) 재귀에 대한 기본적인 이해가 있다면, 어렵지 않게 풀 수 있을 문제지만, 매개 변수 설정에 있어 어려움이 있었다.

4) backtrack(temp, level)에서 temp자리에 어떠한 값을 넣어야 하는지 깊이 있게 고민해 보는 과정이 필요하다.

 

한계점 및 개선사항

초기에 매개변수에 (temp 연산자 vec[i])를 넣는 것을 생각하지 못해 어려움을 겪었다.

temp=temp 연산자 vec[i] 를 넣은 후 재귀를 수행하니 문제점이 다양하게 발생하였다. 

Backtracking의 기본 뼈대를 코딩하는 데는 어려움이 없으나, 아직 한번에 문제를 해결하는 것은 어려운 것 같다.

조금 더 많은 예제를 통해 준비를 할 필요성을 느꼈다.

 

github.com/pearlcrum/CodingTest/tree/main