백준 15658 (연산자 끼워넣기2)

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

15658번: 연산자 끼워넣기 (2)

해당 문제는 N의 정수가 주어지며 N개의 수로 이루어진 수열이 주어진다. 마지막 줄에는 연산자의 개수가 주어지게 되는데 이때 4개의 숫자가 주어지며 각각의 수가 의미하는 것음 사칙연산자의 개수와 같다.

위와 같은 입력이 주어질 때 아래의 조건을 만족시키면서 N개의 수를 모두 연산한 결과 값들 중 최대값과 최소값을 구하는 문제이다.

조건은 다음과 같다.

1. 주어진 연산자는 모두 사용하지 않아도 된다 (따라서 수열을 이용한 모든 연산자 대입)

2. 계산시에는 무조건 수열의 앞에서 부터 계산하기 시작하여야 한다.

 

주의 사항 :

가장 처음에 char vector를 만들어 주어진 연산자를 문자열로 만들어 해당 문자열을 가지고 순열을 구하는 형식으로 풀이 했더니 런타임 애러발생, 왜냐하면 연산자는 수열의 최대크기 11 보다 크거나 같기 때문에 연산량이 재귀 한번 수행시 마다 매우 늘어남 따라서 다른 로직이 필요

현재 사용한 방법은 int [4] 의 배열을 사용하여 순열을 구할 때 해당 배열의 값을 -- 하여 연산자의 사용을 check 한 뒤 재귀가 끝나서 돌아올 경우 배열의 값을 ++ 해주는 과정을 통해 원상복귀 시킴 이와 같이 순열을 구하여 푸는 방식으로 접근하였다.

 

풀이 :

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<int> nList;
int operList[4];
long long maxx = -99999999999;
long long minn = 99999999999;

void dfs(int level, long long sum){

	if (level == n){
		if (sum > maxx) maxx = sum;
		if (sum < minn) minn = sum;
		return;
	}

	for (int i = 0; i < 4; ++i){
		if (operList[i] <= 0) continue;
		operList[i]--;
		if (i == 0) dfs(level + 1, sum + nList[level]);
		else if (i == 1) dfs(level + 1, sum - nList[level]);
		else if (i == 2) dfs(level + 1, sum * nList[level]);
		else if (i == 3) dfs(level + 1, sum / nList[level]);
		operList[i]++;
	}

}


int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;

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

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

	dfs(1, nList[0]);

	cout << maxx << endl;
	cout << minn << endl;
}