알고리즘 :: 백준 :: Bruteforce :: 14888 :: 연산자 끼워넣기

문제

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

문제접근

• 주어진 N-1개의 연산자를 이용해서 결과가 최대인 경우와 최소인 경우의 결과값을 구하면 된다.
• 완전탐색(Bruteforce)으로 풀 수 있는 문제다.
  • N의 범위가 11까지로 짧다.
  • 주어지는 숫자의 범위가 100까지로 작으며, 중간 연산 결과가 10억을 넘지 않는다.
• C++의 next_permutation() 함수를 이용하면 아주 쉽게 풀 수 있다.
  1. 주어지는 연산자를 덧셈 = 0, 뺄셈 = 1, 곱셈 = 2, 나눗셈 = 3으로 넘버링 한 뒤 개수만큼 임의의 컨테이너에 넣어준다.
     • e.g) 3 1 1 2라면, {0 0 0 1 2 3 3}이 저장된다.
  2. next_permutation() 함수를 이용해서 모든 순열에 대해 연산하고 그 결과를 비교해서 max()와 min()함수를 이용해서 갱신한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

static int N, op_plus, op_minus, op_mult, op_div, num[11];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> num[i];
    cin >> op_plus >> op_minus >> op_mult >> op_div;

    vector<int> op;
    for (int i = 0; i < op_plus; ++i)  op.push_back(0);
    for (int i = 0; i < op_minus; ++i) op.push_back(1);
    for (int i = 0; i < op_mult; ++i)  op.push_back(2);
    for (int i = 0; i < op_div; ++i)   op.push_back(3);

    // `answerMAX`와 `answerMIN`의 초기값을 잘 설정해주지 않으면 경계값에서 반례가 존재한다.
    int answerMAX = INT32_MIN, answerMIN = INT32_MAX, temp = num[0];
    do {
        for (int i = 0; i < N - 1; ++i) {
            switch(op[i]) {
                case 0: temp += num[i + 1]; break;
                case 1: temp -= num[i + 1]; break;
                case 2: temp *= num[i + 1]; break;
                case 3: temp /= num[i + 1]; break;
            }
        }
        answerMAX = max(answerMAX, temp);
        answerMIN = min(answerMIN, temp);
        temp = num[0];
    } while (next_permutation(begin(op), end(op)));

    cout << answerMAX << '\n' << answerMIN << '\n';
}

결과