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

문제링크
https://www.acmicpc.net/problem/14888

📂 분류

순열 구현

💡 풀이

이 문제는 풀이 방식이 여러가지 존재할 것 같은데 나는 순열을 통해 풀었다.

연산자 개수를 입력 받으면서 op라는 vector에 연산자 개수 만큼 아래와 같이 연산자를 저장한다.

연산자가 +일 경우 0
연산자가 -일 경우 1
연산자가 *일 경우 2
연산자가 /일 경우 3

저장을 한 후 next_permutation함수를 이용해 순열을 구하고 우선 순위가 없기 때문에 수열 차례대로 연산을 한다. 그리고 max, min 값을 구한다.

💻 코드

//
//  14888.cpp
//  test
//
//  Created by 주성호 on 2022/01/26.
//  Copyright © 2022 주성호. All rights reserved.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> num, numberOfOperator(4);
vector<int> op;

void insertOperator(int n, int c) {
  for (int i = 0; i < n; i++) {
    op.push_back(c);
  }
}

void inputData() {
  int N;
  cin >> N;

  num.reserve(N);

  while (N--) {
    int n;
    cin >> n;
    num.push_back(n);
  }

  for (int i = 0; i < 4; i++) {
    cin >> numberOfOperator[i];
    insertOperator(numberOfOperator[i], i);
  }
}

int main() {
  inputData();
  int max_value = -INT_MAX, min_value = INT_MAX;
  do {
    int temp = num[0];
    for (int i = 1; i < num.size(); i++) {
      if (op[i - 1] == 0) {
        temp += num[i];
      } else if (op[i - 1] == 1) {
        temp -= num[i];
      } else if (op[i - 1] == 2) {
        temp *= num[i];
      } else {
        temp /= num[i];
      }
    }
    max_value = max(max_value, temp);
    min_value = min(min_value, temp);
  } while (next_permutation(op.begin(), op.end()));

  cout << max_value << "\n" << min_value << '\n';

  return 0;
}