[Beakjoon] 21943 연산 최대로 (C++)

문제 링크

BOJ 21943 : 연산 최대로

문제

• N개의 수와 +, *연산자가 주어진다.

• +와 *의 연산자 우선순위는 동일하다.

• 괄호의 사용 가능 개수는 무제한이다.

• 주어진 수와 연산자를 이용해 구할 수 있는 최대값을 출력한다.

풀이

숫자의 순서와 연산자의 순서를 무작위로 바꿀 수 있다. 따라서 모든 경우에 대한 연산을 진행해봐야 한다.

next_permutation함수를 이용하여 숫자와 연산자의 가능한 순서를 만들어낸다.

더하기와 곱하기의 연산자 우선순위가 동일하다는 가정이기 때문에 연산자와 숫자의 순서만 정의하고 순서대로 계산하면 모든 경우에 대한 결과값을 확인할 수 있다.

코드

#include<bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

int N,P,Q;
vector<int> V;
vector<char> OP;

int cal(vector<int> v){
    vector<int> vv;
    int max_result=0;
    do{
        vv.clear();
        int tmp = V[0];
        for(int i=0; i<OP.size(); i++){
            if(OP[i]=='+') tmp+=V[i+1];
            else {
                vv.push_back(tmp);
                tmp=V[i+1];
            }
        }
        if(tmp!=0) vv.push_back(tmp);
        
        int result = vv[0];
        for(int i=1; i<vv.size(); i++){
            result*=vv[i];
        }
        max_result = max(max_result, result);
    }while(next_permutation(OP.begin(), OP.end()));

    return max_result;
}

void Solve() {
    cin>>N;
    int n;
    for(int i=0; i<N; i++){
        cin>>n; V.push_back(n);
    }
    cin>>P>>Q;
    for(int i=0; i<P; i++) OP.push_back('+');
    for(int i=0; i<Q; i++) OP.push_back('*');
    sort(V.begin(), V.end());
    sort(OP.begin(), OP.end());

    int ans=0;
    do{
        int result=cal(V);
        ans = max(ans, result);
    } while(next_permutation(V.begin(), V.end()));

    cout<<ans;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}