백준 14888 c++ "연산자 끼워넣기" -PlusUltraCode-

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

 

 

[필자 사고]

연산자를 끼워넣어 최대값 혹은 최소값을 만들어야 되는 문제이다.

현재 N의 값은 최대11이므로 시간복잡도 측면에서 너그럽다.

 

필자는 DFS를 이용하여 조합알고리즘을 작성하였다.

 

글로 설명하자면  + - * / 가 있을때 하나하나를 숫자 사이에 배치해 둔다.

DFS알고리즘을 이용하면 일단 하나의 문장을 완성하고 

마지막 부분만 연산자를 거둔뒤 사용안한 연산자를 넣는 방식으로 코드를 작성하였다.

 

주의할 점은 DFS의 매개변수를 어떻게 설정하는지가 중요하다.

 

아래는 필자가 작성한 코드해설이다.

 

코드 흐름 설명:

1. 변수 및 배열 초기화:
   • arr는 입력된 숫자들을 저장하는 배열입니다.
   • buho는 각 연산자의 개수를 저장하는 배열로, 덧셈, 뺄셈, 곱셈, 나눗셈의 순서로 연산자의 수를 입력받습니다.
   • buhoCount는 각 연산자가 몇 번 사용되었는지를 추적하는 배열입니다.
   • maxNum은 계산 결과 중 최댓값을 저장하고, minNum은 최솟값을 저장합니다.
2. 입력 함수 (Input):
   • 첫 번째로 숫자의 개수와 해당 숫자들을 arr 배열에 저장합니다.
   • 두 번째로 각 연산자의 개수를 입력받아 buho 배열에 저장합니다.
3. 계산 함수 (calculateNumber):
   • 주어진 숫자들과 연산자에 따라 계산을 수행하는 함수입니다.
   • 덧셈, 뺄셈, 곱셈, 나눗셈 중 해당 연산자를 선택하여 두 숫자의 계산을 수행하고 결과를 반환합니다.
4. DFS 함수 (DFS):
   • 이 함수는 DFS 알고리즘을 사용하여 가능한 모든 연산 순서를 탐색합니다.
   • 매 재귀 호출마다 현재까지의 연산 결과를 기반으로 다음 숫자에 대해 연산을 수행합니다.
   • 모든 숫자를 사용한 후, 최종 결과가 최대값 또는 최소값인지 비교하여 maxNum과 minNum을 업데이트합니다.
   • 각 연산자가 몇 번 사용되었는지를 추적하면서, 사용 가능하면 연산을 하고, 재귀 호출이 끝난 후에는 해당 연산자의 사용 횟수를 줄입니다.
5. 게임 시작 함수 (GameStart):
   • DFS를 호출하여 처음부터 가능한 모든 경로를 탐색하고, 최종적으로 최대값과 최소값을 출력합니다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<int> arr;
vector<int> buho;
vector<int> buhoCount;
int N;
int startNumber;
int maxNum = INT_MIN;
int minNum = INT_MAX;
void Input() {
	cin >> N;
	arr.resize(N);
	buho.resize(4);
	buhoCount.resize(4,0);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	startNumber = arr[0];
	for (int i = 0; i < 4; i++) {
		cin >> buho[i];
	}
}

int calculateNumber(int allNum,int number, int bh) {
	int num = allNum;
	if (bh == 0) {
		num += number;
	}
	else if (bh == 1) {
		num -= number;
	}
	else if (bh == 2) {
		num *= number;
	}
	else if (bh == 3) {
		num /= number;
	}

	return num;
}


void DFS(int numberIdx, int allNum ,int bh) {

	if (numberIdx == N-1&&bh!=-1) {
	
		if (maxNum < allNum) {
			maxNum = allNum;
		}
		if (minNum > allNum) {
			minNum = allNum;
		}
	
		buhoCount[bh]--;
		
		return; 
	}
	
	for (int i = 0; i < 4; i++) {

		if (buho[i] -buhoCount[i]!=0) {
			buhoCount[i]++;
			int number=calculateNumber(allNum,arr[numberIdx+1], i);
			DFS(numberIdx + 1, number , i);
		}
	}

	if (bh == -1) {
		return;
	}
	buhoCount[bh]--;
}

void GameStart() {
	DFS(0, startNumber, -1);
	cout << maxNum << '\n';
	cout << minNum << '\n';
}


int main(void) {

	Input();
	
	GameStart();
	
}