언제나 처음처럼

[문제 링크]

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

간단한 백트래킹 문제였다.

기저사례는 시작 인덱스가 수열의 끝에 도달하는 경우로 설정하였고,

기저사례에 도달할 경우 현재까지 계산된 값으로 최소값과 최대값을 갱신하도록 구현하였다.

#include <iostream>
#include <vector>
using namespace std;

int minVal = 1987654321;
int maxVal = -1987654321;

enum class Operator
{
	Plus,
	Minus,
	Multiple,
	Division
};

void backtracking(vector<int>& arr, vector<int>& operatorArr, int start, int value)
{
	if (start == arr.size())
	{
		minVal = min(minVal, value);
		maxVal = max(maxVal, value);
		return;
	}

	for (int i = 0; i < 4; i++)
	{
		if (operatorArr[i] == 0) continue;
		
		int nextValue = value;

		switch (i)
		{
		case (int)Operator::Plus:
			nextValue += arr[start];
			break;

		case (int)Operator::Minus:
			nextValue -= arr[start];
			break;

		case (int)Operator::Multiple:
			nextValue *= arr[start];
			break;
			
		case (int)Operator::Division:
			nextValue /= arr[start];
			break;
		}

		operatorArr[i]--;
		backtracking(arr, operatorArr, start + 1, nextValue);
		operatorArr[i]++;
	}
}

int main(void)
{
	int N;
	cin >> N;

	vector<int> arr(N);

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	vector<int> operatorArr(4, 0);
	cin >> operatorArr[0] >> operatorArr[1] >> operatorArr[2] >> operatorArr[3];

	backtracking(arr, operatorArr, 1, arr[0]);

	cout << maxVal << '\n' << minVal;

	return 0;
}

[문제 링크]

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

간단한 백트래킹 문제였다.

이전에 담은 숫자를 중복으로 담지 않기 위해 vector<bool>에 담은 숫자를 마킹하는 방식을 사용하였다.

기저사례는 vector<int> 크기가 M과 같아지는 경우로 설정하였고,

기저사례에 도달할 경우 재귀를 수행하지 않고 vector에 담긴 원소를 출력하는 방식으로 구현하였다.

#include <iostream>
#include <vector>
using namespace std;

int N, M;

void backtracking(vector<int>& backpack, vector<bool>& picked)
{
	if (backpack.size() == M)
	{
		for (auto a : backpack)
		{
			cout << a << ' ';
		}
		cout << '\n';

		return;
	}
	
	for (int i = 1; i <= N; i++)
	{
		if (picked[i]) continue;

		backpack.push_back(i);
		picked[i] = true;
		backtracking(backpack, picked);
		backpack.pop_back();
		picked[i] = false;
	}
}

int main(void)
{
	cin >> N >> M;

	vector<int> backpack;
	vector<bool> picked(N+1, false);
	backtracking(backpack, picked);

	return 0;
}