[백준 - 14888] 연산자 끼워넣기 [C++]

1. 문제

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

2. 풀이과정

문제 제목처럼 수들 사이에 연산자를 끼워넣어서 계산해보며 최댓값, 최솟값을 갱신해주면 된다.

주어진 연산자들을 나열할 수 있는 모든 경우의 수에 대해 식의 값을 계산해보면 된다.

[코드설명]

opers 는 연산자들을 저장하는 벡터이다. 

덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수가

2 1 1 1로 주어졌다면 opers는 아래와 같다.

opers = { '+', '+', '-', '*', '/' }

 

dfs함수는 opers의 연산자들을 나열할 수 있는 모든 경우의 수를 생성해준다.

위의 opers를 예로 들면 아래와 같다.

+ + - * /

+ + - / *

+ + / - *

      .

      .

      .

 

calculate함수는 나열된 연산자들을 이용해 앞에서부터 계산한 식의 값을 반환해준다.

 

문제에서 유의할 점은 계산되는 식의 결과가 항상 -10억보다 크거나 같고, 10억보다 작거나 같으므로

초기 최댓값, 최솟값을 잘 설정해줘야한다.

3. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int n;
vector<int> A;
vector<char> opers;
bool visited[11];
int min_v = 1000000000, max_v = -1000000000;

int calculate(vector<char>& o) {
    int ret = A[0];
    for(int i=1; i<n; i++) {
        if(o[i-1] == '+') ret += A[i];
        if(o[i-1] == '-') ret -= A[i];
        if(o[i-1] == '*') ret *= A[i];
        if(o[i-1] == '/') ret /= A[i];
    }
    return ret;
}

void dfs(vector<char>& v, int depth) {
    if(depth == n-1) {
        int result = calculate(v);
        max_v = max(max_v, result);
        min_v = min(min_v, result);
        return;
    }
    for(int i=0; i<n-1; i++) {
        if(!visited[i]) {
            visited[i] = true;
            v.push_back(opers[i]);
            dfs(v, depth+1);
            visited[i] = false;
            v.pop_back();
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=0; i<n; i++) {
        int tmp;
        cin >> tmp;
        A.push_back(tmp);
    }
    for(int i=0; i<4; i++) {
        int tmp;
        cin >> tmp;
        if(i==0) for(int j=0; j<tmp; j++) opers.push_back('+'); 
        if(i==1) for(int j=0; j<tmp; j++) opers.push_back('-');
        if(i==2) for(int j=0; j<tmp; j++) opers.push_back('*');
        if(i==3) for(int j=0; j<tmp; j++) opers.push_back('/');
    }
    vector<char> v;
    dfs(v, 0);
    cout << max_v << "\n" << min_v;
    return 0;
}