백준 14888. 연산자 끼워넣기

알고리즘 중급 문제 중 521 - 브루트 포스 - 순열(연습)

연산자 끼워넣기

1. 간단 설명

N개로 이루어진 수열 A가 주어진다

수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자 +,-,×,÷의 개수가 각각 주어진다

이 수들을 이용하여 만들 수 있는 식의 최대값, 최소값을 구하는 문제

주의사항

• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행
• 나눗셈은 정수 나눗셈으로 몫만 취한다
• 음수를 양수로 나눌 때는 C++14의 기준을 따른다
  • 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다
• 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다.
• 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

2. 예시

N = 6
1 2 3 4 5 6
+ - × ÷
2 1 1 1 

다음과 같이 주어졌을 때

최댓값: 1-2÷3+4+5×6

최솟값: 1+2+3÷4-5×6

으로 구할 수 있다

3. 알고리즘

필요 변수

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

• 배열 A vector<int> A (1 ≤ A_i ≤ 100)

• N-1개의 연산자의 개수를 저장할 int oper[4] 각각 덧셈, 뺄셈, 곱셈, 나눗셈

• 최대 최소값은 다음과 같은 이유로 int max, min으로 처리 가능하다

연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

알고리즘

연산자 우선순위를 무시하므로, 백트래킹으로 구할 수 있다

N도 최대 11이므로 2초 내에 충분히 가능함

1. N과 A를 입력받는다
2. N-1 개의 연산자들을 입력받는다
3. 백트래킹을 이용하여 N개의 숫자가 조합될 때 까지 내려간다
    3-1. N개의 숫자를 골랐다면, 이 숫자들을 이용해 만든 결과값을 최대최소값과 비교하여 갱신한다
    3-2. 각 연산자가 남아있다면, 
       현재 기록된 수에 해당 연산자로 계산한 값을 추가한다

4. 소스코드

#include <iostream>
#include <vector>

using namespace std;

int N;
vector<int> arr;
int oper[4];

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

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

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

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

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

	recursive(0, arr[0]);

	cout << max_val << '\n' << min_val;

	return 0;
}