🙇‍♀️수식만들기(삼성 SW역량평가 기출문제 : DFS활용)

길이가 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이다.

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

▣ 입력예제 1 
3
5 3 8
1 0 1 0

▣ 출력예제 1
64
23

🚀풀이

연산자의 개수가 총 4개이므로 DFS도 4갈래로 나가야한다.

연산자의 수가 주어졌으므로 연산자의 개수 역시 고려해야한다.

연산자를 사용하고 돌아갈 때는 연산자의 수를 되돌려줘야한다.

void DFS(int L, int res)
{
	if (L == n)
	{
		maxRes = max(maxRes, res);
		minRes = min(minRes, res);
	}
	else
	{
		if (signs[0] > 0)
		{
			signs[0]--;
			DFS(L + 1, res + seq[L + 1]);
			signs[0]++;
		}
		if (signs[1] > 0)
		{
			signs[1]--;
			DFS(L + 1, res - seq[L + 1]);
			signs[1]++;
		}
		if (signs[2] > 0)
		{
			signs[2]--;
			DFS(L + 1, res * seq[L + 1]);
			signs[2]++;
		}
		if (signs[3] > 0)
		{
			signs[3]--;
			DFS(L + 1, res / seq[L + 1]);
			signs[3]++;
		}
	}
}

연산자를 되돌려주는걸 생각하지 못했다… 아쉽다..

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n, minRes = 123456789, maxRes = -1;
vector<int> seq;
int signs[4];
void setting()
{
	cin >> n;
	seq = vector<int>(n + 1);
	for (int i = 1; i <= n; ++i)
		cin >> seq[i];

	for (int i = 0; i < 4; ++i)
		cin >> signs[i];
}

void DFS(int L, int res)
{
	if (L == n)
	{
		maxRes = max(maxRes, res);
		minRes = min(minRes, res);
	}
	else
	{
		if (signs[0] > 0)
		{
			signs[0]--;
			DFS(L + 1, res + seq[L + 1]);
			signs[0]++;
		}
		if (signs[1] > 0)
		{
			signs[1]--;
			DFS(L + 1, res - seq[L + 1]);
			signs[1]++;
		}
		if (signs[2] > 0)
		{
			signs[2]--;
			DFS(L + 1, res * seq[L + 1]);
			signs[2]++;
		}
		if (signs[3] > 0)
		{
			signs[3]--;
			DFS(L + 1, res / seq[L + 1]);
			signs[3]++;
		}
	}
}

void solve()
{
	setting();

	DFS(1, seq[1]);

	cout << maxRes << '\n';
	cout << minRes << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고