숫자 만들기

N개의 숫자, ‘+, -, x, /‘ 의 연산자 카드를 연산자의 우선 순위를 고려하지 않고 차례대로 계산
연산 결과의 최대값, 최소값의 차이를 구하는 문제이다.

N은 3 이상 12 이하의 정수 -> 연산자가 들어갈 공간의 수는 2 이상 11 이하
N이 최대인 12개 인 경우 각 연산자의 순열 값은 단순 계산 했을 때, 4^11 = 2*22 = 약 4,000,000 이면서
연산자의 수가 4개 이므로 중복된 경우를 제외 했을때 4백만보다 작다고 판단할 수 있다.

따라서, 이 문제는 숫자의 위치를 고정한 후 사용 할 수 있는 연산자에 대해 순열을 구현한 후
각 경우에 대해 계산하여 최대, 최소값을 찾는 알고리즘을 구현하면 된다.

• 중복 사용을 방지한 순열의 구현에 대해 dfs로 구현했으며 visit 배열을 통해 각 연산자의 남은 수를 체크했다.

이 문제는 과연 모든 경우의 수를 순열로 구현했을 때 worst case 시간초과가 나지 않을까? 라는 의문을
계산을 통해 확신을 가지고 구현한다면 빠른 시간내에 해결 할 수 있다.

#include<iostream>
#include<vector>
#define MAX_VALUE 100000007
using namespace std;

int N;
int visit[4];
vector<int> nums;
int max_v, min_v;

int cal(int now, int next, int c) {
    if (c == 0) return now + next;
    else if (c == 1) return now - next;
    else if (c == 2) return now * next;
    else return now / next;
}

void dfs(int depth, int now) {
    if (depth == N) { // dfs 종료 조건
        if (max_v < now) max_v = now;
        if (min_v > now) min_v = now;
        return;
    }

    for (int i = 0; i < 4; i++) {
        if (visit[i] == 0) continue;
        visit[i]--;
        dfs(depth + 1, cal(now, nums[depth], i));
        visit[i]++;
    }
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    cin >> T;

    for (test_case = 1; test_case <= T; ++test_case)
    {
        max_v = -1 * MAX_VALUE;
        min_v = MAX_VALUE;

        cin >> N;
        int num;
        for (int i = 0; i < 4; i++) {
            cin >> num;
            visit[i] = num;
        }

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

        dfs(1, nums[0]);

        cout << "#" << test_case << " " << (max_v - min_v) << "\n";

        nums.clear();
    }
    return 0;
}