[백준] 14888번 연산자 끼워넣기 (C++)

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

 

 

이 문제는 N개의 수열이 주어지고 4개의 연산자에 대해 각각의 개수가 주어졌때 연산을 하되 연산순서를 무시하고 앞에서부터

차례대로 계산을 하여 최댓값을 출력하는 문제이다.

 

문제 조건에서 수열의 개수 N이 최대 11이며 연산자의 개수의 합은 최대 N-1 인것을 보고

수가 굉장히 작기 때문에 모든 경우의 수를 구하면 되겠다고 생각을 하였다.

 

또한 연산자의 순서에 따라서 값이 달라지기 때문에 재귀 형식의 백트래킹으로 구현하는 것이

더 간단하게 구현될 수 있다고 생각했다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

int dx[] = {0 ,0, -1, 0, 1, 1, -1, -1, 1};
int dy[] = {0, -1, 0, 1, 0, -1, 1, -1, 1};
int N, pluses, minuses, mult, divi;
vector<int> v;
int arr[4];
int maxval = -MAX;
int minval = MAX;

void dfs(int cnt, int val) {
    if(cnt == N-1) {
        maxval = max(val, maxval);
        minval = min(val, minval);
        return;
    }

    if(pluses > 0) {
        pluses--;
        dfs(cnt+1, val + v[cnt+1]);
        pluses++;
    }

    if(minuses > 0) {
        minuses--;
        dfs(cnt+1, val - v[cnt+1]);
        minuses++;
    }

    if(mult > 0) {
        mult--;
        dfs(cnt+1, val * v[cnt+1]);
        mult++;
    }

    if(divi > 0) {
        divi--;
        dfs(cnt+1, val / v[cnt+1]);
        divi++;
    }
}

void solve() {
    dfs(0, v[0]);

    cout << maxval << endl << minval;
}

void input() {
    cin >> N;

    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        v.push_back(a);
    }

    cin >> pluses >> minuses >> mult >> divi;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}