[백준 14888] 연산자 끼워넣기

문제출처: https://www.acmicpc.net/problem/14888

삼성전자 A형 기출문제입니다.

풀이

백트래킹을 이용하여 풀 수 있습니다.

cnt를 선언하여 숫자가 모두 사용되었는지 체크합니다.

최초에 일단 계산을 하려면 첫번째값이 필요하므로, 첫번째 값과 첫번째값이 사용되었음을 나타낼수 있게 cnt+1 두 변수를 매개변수로하는 함수를 선언하여 백트래킹으로 연산을 하면됩니다.

헷갈리시는 분들은 아래 경우처럼 식을 작게해서 이해하시고 식으로 표현해보시면좋을 것같습니다.

3

1 2 3

1 0 1 0

코드

#include<iostream>
#include<algorithm>
using namespace std;
int min_val = 1000000001;
int max_val = -1000000001;
int arr[12];
int op[4];
int n;
void func(int num, int cnt);
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	for (int i = 0; i < 4; i++)
		cin >> op[i];
	//첫 숫자와
	int num = arr[0];
	//첫숫자를 배치하고 연산할준비하므로
	//ex)"1+" 상태여서 숫자한개썼으므로 cnt=1로시작
	func(num, 1);
	cout << max_val << endl << min_val << endl;

}
void func(int num, int cnt)
{
	//숫자를 다 썼으면
	if (cnt == n)
	{
		max_val = max(max_val, num);
		min_val = min(min_val, num);
		return;
	}
	//모든 연산자돌면서확인
	for (int i = 0; i < 4; i++)
	{
		//연산자가 있을 때만 연산합시다.
		if (op[i]) {
			if (i == 0)
			{
				//연산 할거기때문에 연산자 횟수-1
				op[i]--;
				//현재값과 현재 더해야하는 피연산자의 index더함
				func(num + arr[cnt], cnt + 1);
				//백트래킹
				op[i]++;
			}
			if (i == 1)
			{
				op[i]--;
				func(num - arr[cnt], cnt + 1);
				op[i]++;
			}
			if (i == 2)
			{
				op[i]--;
				func(num * arr[cnt], cnt + 1);
				op[i]++;
			}
			if (i == 3)
			{
				op[i]--;
				func(num / arr[cnt], cnt + 1);
				op[i]++;
			}
		}
	}
}

결과