백준 14888_연산자 끼워넣기(C++)

 

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

14888번: 연산자 끼워넣기

[문제 풀이]

문제의 해결법은 브루트포스였던 것 같습니다.

배열 A를 재귀로 도는 방식으로 브루트포스를 구현하였습니다.

 

이 코드의 핵심은

temp = value + A[idx];
oper[j]--;
solution(temp, idx + 1);
oper[j]++;

입니다.

 

이처럼 사칙연산 배열 oper의 값을 +, - 해주며 A 배열의 마지막 값까지 계산이 되었을 때 최댓값, 최솟값을 비교하여 문제를 해결하였습니다.

[코드]

#include<iostream>

using namespace std;

int N;
long long max_result = -987654321, min_result = 987654321;
int A[11];
int oper[4];

void solution(long long value, int idx) {

	if (idx == N) {
		if (value > max_result)
			max_result = value;
		if (value < min_result)
			min_result = value;
		return;
	}

	long long temp;

	for (int j = 0; j < 4; j++) {

		if (oper[j] == 0)
			continue;

		if (j == 0) {
			temp = value + A[idx];
			oper[j]--;
			solution(temp, idx + 1);
			oper[j]++;
		}
		else if (j == 1) {
			temp = value - A[idx];
			oper[j]--;
			solution(temp, idx + 1);
			oper[j]++;
		}
		else if (j == 2) {
			temp = value * A[idx];
			oper[j]--;
			solution(temp, idx + 1);
			oper[j]++;
		}
		else if (j == 3) {
			temp = value / A[idx];
			oper[j]--;
			solution(temp, idx + 1);
			oper[j]++;
		}

	}
}

int main() {

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]);

	for (int i = 0; i < 4; i++)
		scanf("%d", &oper[i]);

	solution(A[0], 1);

	printf("%lli\n%lli\n", max_result, min_result);

	return 0;

}