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

14888번 연산자 끼워넣기

---

1. 이해하기

• 수와 수 사이에 연산자를 하나씩 넣는데 주어진 수의 순서를 바꾸면 안 된다.
• 연산자는 수의 개수-1 개가 주어지기 때문에 모두 사용해야 한다.
• 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구해야 한다.
• 만들 수 있는 결과를 모두 만들어 보는 완전탐색 문제.

---

2. 구현하기

• 최대인 것과 최소인 것을 반환하기 위하여 구조체를 만든다.

  struct RET {
      int min_val,max_val;
  };

• 연산자를 모두 쓰는데 오버해서 쓰면 최댓값과 최솟값을 반환해준다.

  RET solve(int index, int plus, int minus, int mul, int div, int val) {
      if(plus < 0 or minus < 0 or mul < 0 or div < 0) return {MAX,MIN};
      if(plus == 0 and minus == 0 and mul == 0 and div == 0) return {val,val};
  
      RET ret = {MAX,MIN};
      RET temp = solve(index+1,plus-1,minus,mul,div,val+num[index]);
      ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
      temp = solve(index+1,plus,minus-1,mul,div,val-num[index]);
      ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
      temp = solve(index+1,plus,minus,mul-1,div,val*num[index]);
      ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
      temp = solve(index+1,plus,minus,mul,div-1,val/num[index]);
      ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
      return ret;
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
const int MAX = 1000000000;
const int MIN = -MAX;
struct RET {
    int min_val,max_val;
};
int num[11];

RET solve(int index, int plus, int minus, int mul, int div, int val) {
    if(plus < 0 or minus < 0 or mul < 0 or div < 0) return {MAX,MIN};
    if(plus == 0 and minus == 0 and mul == 0 and div == 0) return {val,val};

    RET ret = {MAX,MIN};
    RET temp = solve(index+1,plus-1,minus,mul,div,val+num[index]);
    ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
    temp = solve(index+1,plus,minus-1,mul,div,val-num[index]);
    ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
    temp = solve(index+1,plus,minus,mul-1,div,val*num[index]);
    ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
    temp = solve(index+1,plus,minus,mul,div-1,val/num[index]);
    ret.min_val = min(ret.min_val,temp.min_val); ret.max_val = max(ret.max_val,temp.max_val);
    return ret;
}

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> num[i];
    int plus,minus,mul,div;
    cin >> plus >> minus >> mul >> div;
    RET ans = solve(1,plus,minus,mul,div,num[0]);
    cout << ans.max_val << '\n' << ans.min_val << '\n';
    return 0;
}