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

해당 문제는 백트래킹 문제로 풀었다.

앞에서 소개한 문제와 거의 비슷한 방식으로 풀었다.

수열을 두고, 수열 각각의 원소에 대해 +, -, *, / 를 차례로 반복문을 돌았다.

1+2+3 

1+2-3

1+2*3

1+2/3

 

1-2+3

1-2-3

1-2*3

1-2/3 

...

이런식으로 구성될 수 있도록 코드를 짰다.

세번정도 틀렸는데, 첫번째로는 정수형을 가장 크게 한다고 unsigned int 라고 잡았는데, 뺄셈이 있기 때문에 음수의값이 나올 수 있다. 그래서 이 부분때문에 틀렸다.

 

두번째로는 43% 정도에서 틀렸습니다가 계속 떴다. 질문게시판을 확인해보니 min_ans, max_ans 값으로 둔 값이 987654321이 정수형의 최대값이 아니어서 틀린 것 같다. 

c++에서는 climits라는 라이브러리에 INT_MAX, INT_MIN 값이 정의되어 있어서 이를 사용해서 푸니 맞았다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

vector<int> v;
int arr[4];
int N;
int min_ans = INT_MAX;
int max_ans = INT_MIN;

void dfs(int cnt, int total) {
	if (cnt == N) {
		min_ans = min(min_ans, total);
		max_ans = max(max_ans, total);
		return;
	}
	for (int i = 0;i < 4;i++) {
		if (arr[i] <= 0) continue;
		arr[i]--;
		if (i == 0) {
			dfs(cnt + 1, total + v[cnt]);
		}
		else if (i == 1) {
			dfs(cnt + 1, total - v[cnt]);
		}
		else if (i == 2) {
			dfs(cnt + 1, total * v[cnt]);
		}
		else if (i == 3) {
			dfs(cnt + 1, total / v[cnt]);
		}
		arr[i]++;
	}
	return;
}

int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 0;i < N;i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}
	for (int i = 0;i < 4;i++) {
		cin >> arr[i];
	}
	dfs(1, v[0]);
	cout << max_ans << endl << min_ans << endl;
	return 0;
}