BOJ 14888 연산자 끼워넣기

문제출처 : https://www.acmicpc.net/problem/14888

1. 문제요약

- N개의 수로 이루어진 수열 A1, A2, ... , An이 주어진다.

- 수 사이에 끼워 넣을 연산자가 N-1개 주어진다.

- 수의 순서는 고정되어 있고 숫자 사이에 연산자를 넣어서 만들 수 있는 최대값과 최솟값을 출력

- 수식은 +, -, *, / 순이다.

- 2 <= N <= 11

2. 접근방법

- 조합!

- 10! / (덧셈 연산자 갯수)! * (뺄셈 연산자 갯수)! * (곱셈 연산자 갯수)! * (나눗셈 연산자 갯수)!

3. 시간복잡도

- 10! / (덧셈 연산자 갯수)! * (뺄셈 연산자 갯수)! * (곱셈 연산자 갯수)! * (나눗셈 연산자 갯수)!

4. 회고

- 문제에서 음수 / 양수 인 경우 음수를 양수로 바꾸고 나눗셈 연산을 한 뒤에 다시 음수를 붙이라고 해서 

  진짜 그렇게 했는데.. 굳이 그렇게 안해도 그냥 그런식으로 연산이 되는거였네...

- 종만북에 조합관련된 비슷한 문제가 있었던거 같은데... 찾아봐야지

- 처음에 long long 로 max값을 -2e31 / min값을 2e31-1 로 잡았는데 왜 값이 제대로 안들어가지??

- 아.. 음... 엄청 멍청했군.... 2e31 은 2뒤에 0이 31개 있다는 뜻인데 왜 2^31으로 생각했지 ㅋㅋ

소스코드

#include<iostream>
using namespace std;

int n, a[12], s[4];
long long ans_max = -1000000000, ans_min = 1000000000;

void dfs(int cnt, int sum){
	if (cnt == n - 1){
		if (sum < ans_min)
			ans_min = sum;
		if (ans_max < sum)
			ans_max = sum;
		return;
	}

	if (s[0] > 0){
		s[0]--;
		dfs(cnt + 1, sum + a[cnt + 1]);
		s[0]++;
	}
	if (s[1] > 0){
		s[1]--;
		dfs(cnt + 1, sum - a[cnt + 1]);
		s[1]++;
	}
	if (s[2] > 0){
		s[2]--;
		dfs(cnt + 1, sum * a[cnt + 1]);
		s[2]++;
	}
	if (s[3] > 0){
		s[3]--;
		dfs(cnt + 1, sum / a[cnt + 1]);
		s[3]++;
	}
}

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < 4; i++)
		cin >> s[i];

	dfs(0, a[0]);
	cout << ans_max << "\n";
	cout << ans_min << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]