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

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

접근 방식은 비교적

간단하다.

 

초기값을 arr[0]로잡았다.

왜냐하면 연산자의 갯수는 숫자의 갯수보다 작기 때문이 첫번째 이유고.

두 번째 이유는 첫 번째 숫자는 계산할 필요가 없기 때문이다.

보통 덧셈, 뺄셈, 곱셈, 나눗셈...등등을 계산할때,

첫번째는 계산하지 않고

첫번째 에 두번째 숫자를 계산한다.

즉,

3  + 4 라는 식이 존재한다면

3은 계산하지 않고

+ 때도 계산하지 않는다.

4가 들어왔을때 비로서 두 개의 숫자는 더해진다.

즉, 3 + 4 가 완성된다.

 

이런 접근으로 접근한다면 쉽게 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[20];
int mx = -1000000000;
int mn =  1000000000;

void go(int index,int plus ,int minus,int multi, int div,int result) {

  if (index == n-1) {
    mx = max(mx,result);
    mn = min(mn,result);
    return;
  }


  if (plus > 0) {
  go(index+1,plus-1,minus,multi,div,result+arr[index+1]);
  }

  if (minus > 0) {
  go(index+1,plus,minus-1,multi,div,result-arr[index+1]);
  }

  if (multi > 0) {
   go(index+1,plus,minus,multi-1,div,result*arr[index+1]);
  }

  if (div > 0) {
  go(index+1,plus,minus,multi,div-1,result/arr[index+1]);
  }
  
}

int main(void) {    
  ios_base::sync_with_stdio(false); 
  cin.tie(NULL);

  cin >> n;

  for(int i = 0;i <n;i++) {
    cin >> arr[i];
  }

  int plus;
  int minus;
  int multi;
  int div;

  cin >> plus >> minus >> multi >> div;

  go(0,plus,minus,multi,div,arr[0]);
  
  cout << mx << "\n";
  cout << mn << "\n";
}

 

덧셈, 뺄셈, 곱셈, 나눗셈을 변수로 값을 받게 했다.

뭐 다른 방법이 있을 수도 있겠지만 이 방법이 훨씬 간단하고 쉽기 때문이다.

왜냐하면 

문제에서 연산자들의 갯수들을 제시했기 때문이다.

즉, 덧셈은 1이라는 소리는 덧셈은 1번밖에 하지 못한다는 소리가 된다.

 

그래서 총 4개의 식이 완성되었다.

근데 문제는 이 연산자의 갯수가 0이되면 메소드가 실행이 되게 하면 안된다.

그래서 연산자에 x>0라는 식을 추가해주었다.

여기서 x는 미지수다.(미지수는 변수가 아니다. 미지수는 알수 없는 값.)

그러면 최종적으로 값들이 계산되어서 나온다.

그것을 놓치지 않고

적절히 최댓값, 최솟값을 계산해준다음

출력해주면 답이 된다.

 

여기서 의문인게 연산자 우선순위는 어떻게 될까?

바로 무시한다. 이거 한 문장때문에 위의 방법이 가능하게 된다.

물론, 범위가 작아서 어느정도 가능했긴 했지만 말이다.

 

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int main(void) {
	int N;
	int A[13];
	int op[4]; // + - * /
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
		scanf("%d", &A[i]);
	scanf("%d %d %d %d", &op[0], &op[1], &op[2], &op[3]);
	vector<int> op_brute;
	for (int i = 0; i < 4; i++)
		while(op[i]--)
			op_brute.push_back(i);
	int mn = 0x7fffffff;
	int mx = 0x80000000;
	do {
		int mid = A[0];
		for (int i = 0; i < N - 1; i++) {
			if (op_brute[i] == 0)
				mid += A[i + 1];
			if (op_brute[i] == 1)
				mid -= A[i + 1];
			if (op_brute[i] == 2)
				mid *= A[i + 1];
			if (op_brute[i] == 3)
				mid /= A[i + 1];
		}
		mx = max(mx, mid);
		mn = min(mn, mid);
	} while (next_permutation(op_brute.begin(), op_brute.end()));
	printf("%d\n%d", mx, mn);
}