수식만들기(삼성 SW역량평가 , DFS) / c & c++ / 제한시간 없음

▣ 문제

길이가 N인 자연수로 이루어진 수열이 주어집니다. 수열의 각 항 사이에 끼워넣을 N-1개의 연산자가 주어집니다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있습니 다.

수열의 순서는 그대로 유지한 채 각 항사이에 N-1개의 연산자를 적절히 배치하면 다양한 수 식이 나옵니다.

예를 들면

수열이 1 2 3 4 5이고 덧셈(+) 1개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 일 때 만들 수 있는 수식은 많은 경우가 존재한다.

그 중 1+2*3-4/5와 같이 수식을 만들었다면 수식을 계산하는 결과는 연산자 우선순위를 따지 지 않고 맨 앞쪽 연산자부터 차례로 계산한다. 수식을 계산한 결과는 1이다. 

N길이의 수열과 N-1개의 연산자가 주어지면 만들 수 있는 수식들 중에서 연산한 결과가 최대 인것과 최소인것을 출력하는 프로그램을 작성하세요.

 

▣ 입력설명

- 첫째 줄에 수의 개수 N(2 ≤ N ≤ 10)가 주어진다. 둘째 줄에 수열이 주어진다. 수열의 값은 100까지이다. 셋째 줄에는 연산자의 각 개수가 차례대로 덧셈(+) 개수, 뺄셈(-) 개수, 곱셈(×) 개수, 나눗셈(÷) 개수로 주어진다. 연산자의 총 개수는 N-1이다.

 

▣ 출력설명

- 첫째 줄에는 최댓값을, 둘째 줄에는 최솟값을 출력한다.

 

▣ 입력 예시

3 5 2 8 1 0 1 0

 

▣ 출력 예시

64 23

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>
using namespace std;

int n, max = -2147000000, min = 2147000000;
int operators[4];
int num[20];

int calculate(int level, int x, int res) {
	int temp;
	if (x == 0) temp = res + num[level + 1];
	else if (x == 1) temp = res - num[level + 1];
	else if (x == 2) temp = res * num[level + 1];
	else temp = res / num[level + 1];
	return temp;
}

void dfs(int level, int res) {
	int i, temp;
	if (level == n - 1) {
		if (res < min) min = res;
		if (res > max) max = res;
	}
	else {
		for (i = 0; i < 4; i++) {
			if (operators[i] == 0) continue;
			temp = calculate(level, i, res);
			operators[i]--;
			dfs(level + 1, temp);
			operators[i]++;
		}
	}
}

int main() {
	int i;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		scanf("%d", &num[i]);
	}
	for (i = 0; i < 4; i++) {
		scanf("%d", &operators[i]);
	}
	dfs(0, num[0]);
	printf("%d %d\n", max, min);
	return 0;
}

DFS의 기준을 레벨으로 설정하고 각 연산자가 가능한 모든 케이스를 탐색한다.

 

.