백준 14888번 : 연산자 끼워넣기

• 분류: 백트래킹

코드

#include <iostream>
using namespace std;

int n;
int max_val = INT32_MIN;
int min_val = INT32_MAX;

void backtrack(int depth, const int a[], int op[], int op_default[]) {
    if(depth==n-1) {
        int total = a[0];
        for(int i=0 ; i<n-1 ; i++) {
            if(op[i]==1) total += a[i+1];
            else if(op[i]==2) total -= a[i+1];
            else if(op[i]==3) total *= a[i+1];
            else total /= a[i+1];
        }
        if(max_val<total) max_val=total;
        if(min_val>total) min_val=total;
    }
    for(int i=0 ; i<n-1 ; i++) {
        if(op_default[i]==0) continue;
        op[depth] = op_default[i];
        op_default[i] = 0;
        backtrack(depth+1, a, op, op_default);
        op_default[i] = op[depth];
    }
}

int main() {
    std::cin >> n;
    int a[n];
    int op_num[4];
    int op[n-1];
    int op_default[n-1];
    for(int i=0 ; i<n ; i++) std::cin >> a[i];
    for(int i=0 ; i<4 ; i++) std::cin >> op_num[i];

    int i;
    for(i=0 ; i<op_num[0] ; i++) op_default[i]=1; // 1 = plus
    for(; i<op_num[0]+op_num[1] ; i++) op_default[i]=2; // 2 = minus
    for(; i<op_num[0]+op_num[1]+op_num[2] ; i++) op_default[i]=3; // 3 = multiply
    for(; i<op_num[0]+op_num[1]+op_num[2]+op_num[3] ; i++) op_default[i]=4; // 4 = divide

    backtrack(0, a, op, op_default);
    std::cout << max_val << '\n' << min_val;
}

• 코멘트
  
  역시 간단한 백트래킹으로 풀 수 있다.
  (n-1)개 연산자를 배열에 저장하고, 재귀를 통해 연산자 순열의 모든 경우를 탐색한다. 탐색의 가장 깊은 곳에서는 그동안 고른 연산자 순서대로 계산을 진행한다.
  
  
• 헤맨 곳
  

  식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.

라고 문제에 써있는데 못 보고 뻘짓하다가 시간을 많이 낭비했다. 문제를 잘 읽도록 하자.