(C++) - 백준(BOJ) 14888번 : 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

backtracking하며 brute force로 푼 문제였습니다.

 

 

 

📕 풀이방법

 1. 연산자를 사용할 수 있으면 해당 연산자를 사용하고 개수를 하나 빼줍니다. 연산을 하고 난 이후에는 사용한 개수를 반납해줍니다(더합니다)

 

 2. 호출할 수 있는 모든 함수를 호출해도 n이 11이하이기 때문에 4^10밖에 안되므로 최적화 없이 간단히 해결할 수 있습니다.

 

---

 

 

📕 Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int n, a[12], opNum[4];
int minNum = INF, maxNum = -INF;

void backtracking(int depth, int num){
    //cout <<"depth, num :  "<< depth << ' ' <<num << '\n';
    if(depth == n) {
        maxNum = max(maxNum, num);
        minNum = min(minNum, num);
        return;
    }
    
    if(opNum[0] > 0){
        opNum[0]--;
        backtracking(depth + 1, num + a[depth]);
        opNum[0]++;
    }
    if(opNum[1] > 0){
        opNum[1]--;
        backtracking(depth + 1, num - a[depth]);
        opNum[1]++;
    }
    if(opNum[2] > 0){
        opNum[2]--;
        backtracking(depth + 1, num * a[depth]);
        opNum[2]++;
    }
    if(opNum[3] > 0){
        opNum[3]--;
        backtracking(depth + 1, num / a[depth]);
        opNum[3]++;
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < 4; i++) cin >> opNum[i];

    backtracking(1, a[0]);
    cout << maxNum << '\n' << minNum;
}