[삼성코테기출문제] 연산자 끼워넣기

연산자 끼워넣기

문제

그동안 노력해온 덕분인지 매우 수월하게 문제를 풀었다. 보자마자 Brute Force로 풀어야겠네! 라고 생각했다. 이제 문제 해석 할 때 어떤 방식으로 풀어야 하는지는 좀 잘 보이기 시작하는 것 같다.

문제 풀이

이 문제에서 유의할 점은 최댓값과 최솟값의 범위를 잘 생각해야한다는 것이었다. 그리고 나눗셈 조건도 잘 생각해야되는 문제였던 것 같은데 내가 쓰는 언어가 C++이라서 고려할 필요가 없는 것 같다. 혹시나 해서 조건에 맞게 계산을 해봤는데 오히려 결과가 안나왔다. 왜그럴까?

입출력 조건

풀이 과정

1. 이 문제도 역시 완전탐색이므로 +,-,*,/ 네가지 연산에 대해서 모두 재귀함수를 시작한다.
2. 지금와서 코드를 다시 리뷰해보니 Process(int n, int total, int idx, int i) 이 매개변수에서 n과 i를 따로둘 필요가 없는 것 같다. 총 숫자가 N개라고 하면 연산은 N-1번 일어나므로 이걸로 재귀함수 종료 조건을 주려고 했는데 i를 이용해도 충분할 것 같다.
3. 재귀함수의 종료 조건
   • n=1이되면 총 계산한 값들 중 최대값과 최소값을 찾아 저장해주고 종료한다.
   • 해당 연산자가 더 이상 사용할 수 없으면 종료한다.
4. 넘겨 받은 인덱스에 따라 해당 인덱스가 의미하는 연산을 해준다.
5. 그리고 또 다음 4가지 연산을 모두 재귀함수로 돌린다.
6. 위 과정을 반복하여 최대값과 최소값을 찾는다.

#include<iostream>

using namespace std;
const int MAX_A = 100;
int N;
long Max = -2000000000, Min = 2000000000;
long A[MAX_A];
int cal[4];

void Input() {
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> A[i];
	for (int i = 0; i < 4; i++)
		cin >> cal[i];
}
//덧셈 뺄셈 곱셈 나눗셈
//int Div(int a, int b) {
//	if (a > 0 && b > 0) return a / b;
//	else if (a < 0 && b>0)return -((-a) / b);
//	else if (a > 0 && b<0)return -(a / (-b));
//	else if (a < 0 && b < 0)return (-a) / (-b);
//}
void Process(int n, int total, int idx, int i) {
	if (n <= 1) {
		if (Max < total)Max = total;
		if (Min > total)Min = total;
		return;
	}
	if (cal[idx] == 0)return;
	int tot;
	if (idx == 0) tot = total + A[i];
	else if (idx == 1) tot = total - A[i];
	else if (idx == 2) tot = total * A[i];
	//else if (idx == 3) tot = Div(total, A[i]);
	else if (idx == 3) tot = total / A[i];
	for (int k = 0; k < 4; k++) {
		cal[idx] -= 1;
		Process(n - 1, tot, k, i + 1);
		cal[idx] += 1;
	}
}
void Solution() {
	Input();
	for (int i = 0; i < 4; i++)
		Process(N, A[0], i, 1);
	cout << Max << "\n" << Min << "\n";
	//cout << (1 << 30);
}
int main() {
	freopen("10.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	Solution();
	return 0;
}