연산자 끼워넣기

작성일 | In

[백준] 14888번 - 연산자 끼워넣기

문제 링크

연산자가 배치될 수 있는 모든 경우의 수를 계산하여 식의 최댓값, 최솟값을 구하는 문제이다.
n이 최대 11이므로 브루트포스로 충분히 풀이할 수 있을거라 생각했다. 아울러 식의 계산이 곱셈, 나눗셈 우선순위 없이 앞에서부터 순차적으로 수행되므로 구현도 별 어려움이 없다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;

vector<int> seq;
int op[4];
int n;
int maxVal=-INT_MAX, minVal=INT_MAX;

void operate(int idx, int acc) {
    if(idx == n) {
        maxVal = maxVal < acc ? acc : maxVal;
        minVal = minVal > acc ? acc : minVal;
        return;
    }

    for(int i=0; i<4; ++i) {
        if(op[i] != 0) {
            int nacc = acc;
            switch(i) {
                case 0: nacc += seq[idx]; break;
                case 1: nacc -= seq[idx]; break;
                case 2: nacc *= seq[idx]; break;
                case 3: nacc /= seq[idx]; break;
            }
            --op[i];
            operate(idx+1, nacc);
            ++op[i];
        }
    }
}

int main(void) {
    scanf("%d", &n);

    seq.resize(n);
    for(int i=0; i<n; ++i)
        scanf("%d", &seq[i]);
    
    for(int i=0; i<4; ++i)
        scanf("%d", &op[i]);

    operate(1, seq[0]);
    printf("%d\n%d", maxVal, minVal);
}
0%