[BOJ] 14888 연산자 끼워넣기

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

Note

수 사이에 연산자를 넣어 최대 최소가 되는 경우를 찾아내는 문제

수는 신경쓰지 않고 연산자를 할당하는 부분에 신경을 기울이면 된다.
또한 연산자의 개수가 정해져 있기 때문에 현재까지 몇개를 할당 해 줬는지 기억을 해줄 필요가 있다
연산자가 n-1개가 아니라 n개라면 맨 앞에 -를 넣는 경우를 생각 해야 하지만 현재 문제는 n-1 개 이기 때문에 고려하지 않아도 된다.
계산식의 우선순위가 없다는 점이 문제의 난이도를 낮춘다.
유의 할 점은 이번 연산자가 / 일때 분모가 0이 되는 경우는 제외해서 연산을 시켜야 한다.
또한 값을 최대 최솟값이 double, long 인경우 연산 결과가 바뀐다, 해당 문제에서는 int형을 전제로 하고 있다.
나눗셈을 신경써서 double로 했더니 테스트 케이스 3의 값이 다르게 나왔다.

n-1개의 배열에 순서대로 값을 넣어가면서 넣는 재귀함수를 구현하면 된다.

알고리즘

1. 수를 받아 배열에 저장하고, 연산자의 수를 입력 받는다.
2. • 에서 / 까지 순서대로 i 칸에 배정하고 연산자의 개수를 저장하는 배열에 해당 위치의 값을 1씩 추가한다.
     2-1. 연산자가 / 인경우 분모가 0이 오게 되는 경우라면 진행하지 않는다.
3. 연산 결과를 최대, 최솟값과 비교하면서 값을 갱신한다.
4. 출력 

소스코드

#include <iostream>

using namespace std;

const int MAX = 100;

int opers[4]; // 각 연산자의 갯수
int opnd[MAX]; // 피연산자
int useOper[4]; // 사용한 연산자의 수
int flag[MAX -1]; // 각 자리 연산자
int n;

int resMin = 1000000001, resMax = -1000000000;

void func(int pos)
{
	if (pos + 1 == n)
	{
		int sum = opnd[0];
		for (int i = 1; i < n; i++)
		{
			switch (flag[i - 1])
			{
			case 0:
				sum += opnd[i];
				break;
			case 1:
				sum -= opnd[i];
				break;
			case 2:
				sum *= opnd[i];
				break;
			case 3:
				sum /= opnd[i];
				break;
			}
		}

		if (resMin > sum)
			resMin = sum;
		if (resMax < sum)
			resMax = sum;
	}
	else
	{
		for (int i = 0; i < 4; i++)
		{
			if (useOper[i] + 1 <= opers[i])
			{
				if (i == 3 && opnd[pos + 1] == 0)
					continue;
				useOper[i]++;
				flag[pos] = i;
				func(pos + 1);
				useOper[i]--;
			}
		}
	}
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> opnd[i];

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

	func(0);

	cout << resMax << '\n' << resMin;

	return 0;
}

2019-01-15 16:14:44에 Tistory에서 작성되었습니다.