c++) 백준 14888 백트래킹, 연산자 끼워넣기

14888번: 연산자 끼워넣기 (acmicpc.net)

14888번: 연산자 끼워넣기

 

 

1. 접근

 

수열과 수열의 각 수 사이에 들어갈 연산자가 주어진다.

 

수열은 순서에 맞게 계산해야하므로 사실 고려할게 없다.

 

우리가 고려해야할 것은 주어진 연산자들의 모든 순서와, 그로 인해 계산된 결과들을 출력하는 것 뿐.

 

사실상 연산자들을 선택하는 순열로 생각하면 된다.

 

 

 

 

2. 풀이

 

operands 배열엔 수열을 이루는 수들을 입력받는다.

operators 배열엔 각 연산자(+,-,*,/) 의 수를 입력받는다.

 

우리는 백트래킹 과정에서 가능한 모든 연산자의 순서 조합을 살펴보면 될 것이다.

 

vector로 결과를 저장하는 공간을 생성하고, max/min_element를 이용해 최대와 최솟값을 구했다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 11

using namespace std;

int N;
int operands[MAX]; // 수열
int operators[4]; // 연산자
vector<int> results;

int calc(int op, int result, int val){
    switch(op){
        case 0:
            return result + val;
        case 1:
            return result - val;
        case 2:
            return result * val;
        case 3:
            return result / val;
    }
}

void dfs(int result, int idx){
    if (idx == N){
        results.push_back(result);
        return ;
    }

    for(int i = 0; i < 4; i++){
        if(operators[i]){
            operators[i]--;
            dfs(calc(i, result, operands[idx]), idx+1);
            operators[i]++;
        }
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N;

    int input;

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


    dfs(operands[0],1);
    
    cout << results[max_element(results.begin(),results.end())-results.begin()] << '\n';
    cout << results[min_element(results.begin(),results.end())-results.begin()] << '\n';

    return 0;
}