[모의 SW 역량테스트] 4008. 숫자 만들기

[모의 SW 역량테스트] 숫자 만들기

---

1. 이해하기

• N개의 숫자가 적혀 있는 게임 판이 있고, +,-,*,/ 의 연산자 카드를 숫자 사이에 끼워 넣어 다양한 결과 값을 구한다.
• 연산자의 우선 순위는 고려하지 않고 왼쪽에서 오른쪽으로 차례대로 계산한다.
• 연산자 카드를 사용하여 수식을 계산했을 때, 그 결과가 최대가 되는 수식과 최소가 되는 수식을 찾고, 두 값의 차이를 구하는 문제.
• 완전탐색 문제.

---

2. 구현하기

• 숫자 사이에 모든 연산자를 넣어보며 그 때의 최솟값과 최댓값을 구한다.

  • 연산자는 주어진 갯수만 사용할 수 있으므로 그 이상을 사용한다면 적절한 값을 리턴해준다.

  void set_min_max_val(const RET t, int& min_val, int& max_val) {
      min_val = min(min_val,t.min); max_val = max(max_val,t.max);
  }
  
  RET solve(int index, int plus, int minus, int mul, int div, int res) {
      if(plus < 0 or minus < 0 or mul < 0 or div < 0) return {MAX,-MAX};
      if(plus == 0 and minus == 0 and mul == 0 and div == 0) return {res,res};
  
      int min_val = MAX, max_val = -MAX;
      RET t = solve(index+1,plus-1,minus,mul,div,res+num[index]);
      set_min_max_val(t,min_val,max_val);
      t = solve(index+1,plus,minus-1,mul,div,res-num[index]);
      set_min_max_val(t,min_val,max_val);
      t = solve(index+1,plus,minus,mul-1,div,res*num[index]);
      set_min_max_val(t,min_val,max_val);
      t = solve(index+1,plus,minus,mul,div-1,res/num[index]);
      set_min_max_val(t,min_val,max_val);
      return {min_val,max_val};
  }

• 구한 최댓값과 최솟값의 차이를 구한다.

  int get_diff() {
      RET res = solve(1,oper[0],oper[1],oper[2],oper[3],num[0]);
      return abs(res.min-res.max);
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
struct RET {
    int min,max;
};
const int MAX = 1000000000;
int oper[4];
int num[12];
int N;

int abs(int a) {
    return (a<0)?-a:a;
}

void set_min_max_val(const RET t, int& min_val, int& max_val) {
    min_val = min(min_val,t.min); max_val = max(max_val,t.max);
}

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

    int min_val = MAX, max_val = -MAX;
    RET t = solve(index+1,plus-1,minus,mul,div,res+num[index]);
    set_min_max_val(t,min_val,max_val);
    t = solve(index+1,plus,minus-1,mul,div,res-num[index]);
    set_min_max_val(t,min_val,max_val);
    t = solve(index+1,plus,minus,mul-1,div,res*num[index]);
    set_min_max_val(t,min_val,max_val);
    t = solve(index+1,plus,minus,mul,div-1,res/num[index]);
    set_min_max_val(t,min_val,max_val);
    return {min_val,max_val};
}

int get_diff() {
    RET res = solve(1,oper[0],oper[1],oper[2],oper[3],num[0]);
    return abs(res.min-res.max);
}

void input() {
    cin >> N;
    for(int i = 0; i < 4; i++) cin >> oper[i];
    for(int i = 0; i < N; i++) cin >> num[i];
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << get_diff() << '\n';
    }
    return 0;
}