15658번

15658번 - 연산자 끼워넣기(2)

기존에 있던 연산자 끼워넣기 문제와 똑같다. 다만 최대값과 최소값을 모두 구해야 한다는 차이점이 있다.

N의 범위가 최대 11이기 때문에, 시간복잡도는 최대 4^11 로 완전탐색으로 충분히 구현할 수 있게 된다.

<정답 코드>

#include<iostream>
using namespace std;
int N;
int num[12];
int op[4];
int MAX = -2000000000;
int MIN = 2000000000;
void go(int k,int sum)
{
    if (k == N)
    {
        if (sum > MAX)
            MAX = sum;
 
        if (sum < MIN)
            MIN = sum;
 
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        if (op[i] != 0)
        {
            op[i] -= 1;
 
            if (i == 0)
                go(k + 1, sum + num[k]);
            else if (i == 1)
                go(k + 1, sum - num[k]);
            else if (i == 2)
                go(k + 1, sum*num[k]);
            else
                go(k + 1, sum / num[k]);
 
            op[i] += 1;
        }
    }
 
}
int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> num[i];
    for (int i = 0; i < 4; i++)
        cin >> op[i];
 
    go(1,num[0]);
 
    cout << MAX << endl << MIN << endl;
 
    return 0;
}