14888. 연산자 끼워넣기

 

같은 것을 포함한 순열이라는 느낌을 받고,

이를 구현해보려고 하다가, 잘 안되서 결국 못했다. 조합을 여러번 하는 것으로 구현해보려고 하다가,

너무 복잡해지는 감이있어서, 다시 완전탐색을 시도.

연산자는 최대 10개이고, 같은 연산자라도 다 다르다고 취급하고, 순열의 수를 생각해봤을 때, O(N!)의 시간복잡도를 가진다. 10! = 3,628,800 이므로 충분.

처음에는, 마지막 기저조건(return)에서 모든 결과값을 계산하는데 O(N)시간을 써먹어서 시간이 좀 느리게 나왔다.

#include <cstdio>
int N;
int nums[12];
char opers[12];
int chk = 1 << 12;
char seq[12];

int maxans = -1987654321;
int minans = 1987654321;

int calculate(){
    int res = nums[0];
    for (int i=0; i<N-1; ++i){
        if (seq[i] == '+') res += nums[i+1];
        else if (seq[i] == '-') res -= nums[i+1];
        else if (seq[i] == '*') res *= nums[i+1];
        else if (seq[i] == '/') res /= nums[i+1];
    }
    return res;
}

void dfs(int depth){
    if (depth == N - 1){
        int res = calculate();
        if (maxans < res) maxans = res;
        if (minans > res) minans = res;
        return;
    }
    for (int i=0; i<N-1; ++i){
        if (chk & (1 << i)) continue;
        seq[depth] = opers[i];
        chk |= (1 << i);
        dfs(depth + 1);
        chk &= ~(1 << i);
    }
}

int main() {
    scanf("%d", &N);
    for (int i=0; i<N; ++i) scanf("%d", &nums[i]);
    int cnt = 0;
    int a;
    scanf("%d", &a);
    for (int j=0; j<a; ++j, ++cnt) opers[cnt] = '+';
    scanf("%d", &a);
    for (int j=0; j<a; ++j, ++cnt) opers[cnt] = '-';
    scanf("%d", &a);
    for (int j=0; j<a; ++j, ++cnt) opers[cnt] = '*';
    scanf("%d", &a);
    for (int j=0; j<a; ++j, ++cnt) opers[cnt] = '/';
    
    dfs(0);
    printf("%d\n%d\n", maxans, minans);
    return 0;
}

 

그래서, 함수를 호출할 때 매개변수로 그 결과를 바로 넣어주었더니, 시간도 1 / O(N) 만큼 절감되고, 메모리사용량도 줄일 수 있었다.

#include <cstdio>
int N;
int nums[11];
int ops[4];
int maxans = -1987654321;
int minans = 1987654321;

void dfs(int depth, int res, int idx){
    if (depth == N-1){
        if (maxans < res) maxans = res;
        if (minans > res) minans = res;
        return;
    }
    for (int i=0; i<4; ++i){
        if (ops[i]){
            --ops[i];
            if (i == 0) dfs(depth + 1, res + nums[idx], idx + 1);
            else if (i == 1) dfs(depth + 1, res - nums[idx], idx + 1);
            else if (i == 2) dfs(depth + 1, res * nums[idx], idx + 1);
            else if (i == 3) dfs(depth + 1, res / nums[idx], idx + 1);
            ++ops[i];
        }
    }
}

int main() {
    scanf("%d", &N);
    for (int i=0; i<N; ++i) scanf("%d", &nums[i]);
    for (int i=0; i<4; ++i) scanf("%d", &ops[i]);
    dfs(0, nums[0], 1);
    printf("%d\n%d\n", maxans, minans);
    return 0;
}