[BOJ] 14888 연산자 끼워넣기 - Back Tracking

BOJ 14888 연산자 끼워 넣기 문제.

매우 평범하고도 쉬운 Back Tracking 문제이다.

기존의 Back Tracking 과 똑같이 Branch 의 Return 을 받고, 상태 초기화 후 반복문 돌리니 쉽게 풀어 낼 수 있었다.

연산자 우선순위는 무시한다고 했으므로 단순하게

이전 선택지에 대한 누적 결과를 Param으로 주는 Branch를 진행한다.

Branch Depth 의 끝에 도달했을때가 식을 모두 진행한 결과이므로 이때에 최소값과 최대값을 갱신한다.

진입점에서 맨 처음에 오는 숫자는 이전의 결과가 없으므로 자기 자신을 넣어준다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <vector>

int Operators [4];
int Numbers   [100];

int Max = 0X80000000;
int Min = 0x7FFFFFFF;


void GetBranchResults(int CurIdx, int MaxIdx, int PreResult)
{
	
	if (CurIdx == MaxIdx)
	{
		if (PreResult > Max) Max = PreResult;
		if (PreResult < Min) Min = PreResult;

		return;
	}


	for (int i = 0; i < 4; ++i)
	{

		if (Operators[i] != 0)
		{
			--Operators[i];
			switch (i)
			{
			case 0:
				GetBranchResults(CurIdx + 1, MaxIdx, PreResult + Numbers[CurIdx]); break;
			case 1:
				GetBranchResults(CurIdx + 1, MaxIdx, PreResult - Numbers[CurIdx]); break;
			case 2:
				GetBranchResults(CurIdx + 1, MaxIdx, PreResult * Numbers[CurIdx]); break;
			case 3:
				GetBranchResults(CurIdx + 1, MaxIdx, PreResult / Numbers[CurIdx]); break;

			default:
				break;
			}

			++Operators[i];
		}

	}


}

std::vector<int> Results;

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin.tie(nullptr);

	int InputNumber;
	std::cin >> InputNumber;

	for (int i = 0; i < InputNumber; ++i) std::cin >> Numbers[i];
	for (int i = 0; i < 4; ++i)           std::cin >> Operators[i];

	GetBranchResults(1,InputNumber,Numbers[0]);

	std::cout << Max << '\n';
	std::cout << Min;
}