15658 연산자 끼워넣기(2)

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

연산자의 개수는 N-1보다 많을 수도 있다.

모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며,

주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다.

라는 조건이 추가된 버전

14888 연산자 끼워넣기의 업그레이드 버전

1. 문제

---

간단 설명

N과 N개의 피연산자가 주어지고, 4개의 연산자 개수가 주어진다

피연산자들에 연산자들을 적절히 사용해서 얻을수 있는 최대 최소값을 구하는 문제

• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행

• 나눗셈은 정수 나눗셈으로 몫만 취한다

• 음수를 양수로 나눌 때는 C++14의 기준을 따른다(양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다)

등등 많은 조건들이 달린걸로 봐서는 무수히 많은 문제 수정 요쳥이 있었던 것으로 예상됨

2. 문제 분석

---

필요변수

• 피연산자 개수 N(2 ≤ N ≤ 11)

• A_1, A_2, …, A_N을 저장할 벡터 vector<int> v(1 ≤ A_i ≤ 100)

• 각 연산자들의 개수를 저장할 oper[4] 배열

• ‘연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다’ 라는 조건이 있기 때문에 int형으로 처리가능

• ‘또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.’ 라는 조건이 있기 때문에 중간값을 담는 변수도 int로 처리 가능하다

주의점

• DFS에서 연산자를 사용하고 복원하는 과정에 주의
• 피연산자 0번부터 시작해야한다
• 언제 재귀함수를 탈출할것인지 조건에 주의

알고리즘

1. N과 N개의 피연산자를 입력받아 v에 저장
2. 4개의 사칙연산의 개수를 입력받는다
3. 재귀함수의 매개변수로 (시작 레벨, 피연산자 0)번으로 주고 시작
    3-1. 만약 모든 피연산자를 사용했다면
        - 최대, 최소값을 비교하고 갱신하고 리턴한다
    3-2. 각 사칙연산의 개수가 남아있는지 확인한다
        3-2-1. 남아있다면, 해당 연산자를 한개 사용한다
        3-2-2. 3번 재귀함수를 (시작 레벨 + 1, 현재 사칙연산을 사용한 결과값)을 매개변수로 넘겨주어 호출한다
4. 재귀 함수가 종료되면, 최대 최소값을 출력하고 종료

3. 소스코드

---

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

using namespace std;

int N;
vector<int> v;
vector<int> oper(4);

int min_val = 21e8;
int max_val = -21e8;

void recursive(int level, int result) {
	if (level == N - 1) {
		min_val = min(min_val, result);
		max_val = max(max_val, result);
		return;
	}

	if (oper[0]) {
		oper[0]--;
		recursive(level + 1, result + v[level + 1]);
		oper[0]++;
	}
	if (oper[1]) {
		oper[1]--;
		recursive(level + 1, result - v[level + 1]);
		oper[1]++;
	}
	if (oper[2]) {
		oper[2]--;
		recursive(level + 1, result * v[level + 1]);
		oper[2]++;
	}
	if (oper[3]) {
		oper[3]--;
		recursive(level + 1, result / v[level + 1]);
		oper[3]++;
	}

	return;
}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N;
	v.resize(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

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

	recursive(0, v[0]);

	cout << max_val << endl;
	cout << min_val << endl;

	return 0;
}