백준 14888번 _ 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

주의할점

1. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.

2. 나눗셈은 정수 나눗셈으로 몫만 취한다.

---

풀이방법

c++을 이용한다면 next_permutation함수를 쓰면 간단하다. 나는 c++을 사용하므로 이 방법에 대해서 설명하겠다.

 

1. 덧셈(0), 뺄셈(1), 곱셈(2), 나눗셈(3) 으로 정해둔다.

 

2. next_permutation함수에 넣을 vector에 덧셈의 개수, 뺄셈의 개수, 곱셈의 개수, 나눗셈의 개수대로 정해진 수를 넣어두고 오름차순으로 정렬해둔다.

 

3. next_permutation을 돌리면서 maxValue, minValue를 구한다.

---

 시간

 N<=11, 연산자의 종류는 4개, 숫자는 11개 이므로 4^11에 계산을 하는 경우와 덧셈에 대한 경우인 N을 곱해도 주어진 시간이 2초에 비하면 아주 작은 계산이다.

 

 거기다가 쓸수있는 연산자의 개수는 제한되어있으므로 실제 계산되는 경우의 수는 훨~씬 작을것이다.

---

전체코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;
int N;
vector<int>number;
vector<int>oper;

void Input()
{
	cin >> N;
	int value;
	for (int i = 0; i < N; i++)
	{
		cin >> value;
		number.push_back(value);
	}
	
	for (int i = 0; i < 4; i++)
	{
		cin >> value;
		for(int j =0; j<value; j++)
			oper.push_back(i);
	}
}

int calculate(int a, int b, int op)
{
	if (op == 0)
		return a + b;
	else if (op == 1)
		return a - b;
	else if (op == 2)
		return a * b;
	else if (op == 3)
		return a / b;
}

void solve()
{
	int maxValue = INT_MIN;
	int minValue = INT_MAX;
	sort(begin(oper), end(oper));

	do
	{
		int sum = number[0];
		int idx = 0;
		for (int i = 1; i < (int)number.size(); i++)
		{
			sum = calculate(sum, number[i], oper[idx]);
			idx++;
		}
		maxValue = max(maxValue, sum);
		minValue = min(minValue, sum);
	} while (next_permutation(begin(oper), end(oper)));

	cout << maxValue << endl << minValue << endl;
}

int main()
{
	Input();
	solve();
	return 0;
}

---

후기

C++을 사용하는 친구들이라면 이 문제는 쉽게 풀것같다.