[C++] 백준 14888번: 연산자 끼워 넣기 (브루트 포스)

14888번: 연산자 끼워넣기

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

주어진 연산자를 활용하여 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하여라.

---

시간복잡도 어림하기

브루트 포스 알고리즘

 해당 문제는 수의 위치는 고정되어 있고, 연산자들을 적절히 배치하여 식의 결과를 구하는 문제입니다. 따라서 전체 경우의 수는 연산자들을 일렬로 나열하는 경우의 수와 같습니다. 수의 개수의 최댓값이 11개 이므로 연산자 수의 최댓값은 10개 입니다. 따라서 전체 경우의 수는 10! = 360만 정도 되는 값입니다. 이는 제한 시간 내에 문제를 해결하기 적절한 수치입니다.

---

알고리즘 설계하기

 일반적으로 브루트 알고리즘은 다음과 같은 구조를 가집니다.

1. 기저사례(종료 조건)
2. 로직 실행 및 재귀 호출

 

 가장 먼저 기저 사례를 설계해 봅시다. 이 문제에서 한 케이스에 대해 재귀 호출을 그만 두는 경우는 식을 완성했을 때 입니다. 따라서 idx가 n에 도달했을 때, 식의 최댓값과 최솟값을 갱신하고 탐색을 종료합니다.

 

 재귀 호출을 하는 로직은 어떻게 구성할 수 있을까요? 문제에서 수의 위치는 고정되어있고, 연산자의 위치는 정해지지 않았기 때문에 연산자 배치를 중심으로 고민해봅시다.

 

 현재 위치에 대해 가능한 모든 연산자들을 배치하여 그 결과를 확인해야 하므로 루프를 4번 반복합니다. 각 루프는 현재 위치에 연산자를 삽입할 수 있는지를 확인하고, 가능하다면 연산자를 추가하고 다음 위치로 이동합니다. 코드로는 다음과 같은 형태가 될 것입니다.

for(int i = 0; i < 4; i++){
	if(연산자 개수 배열[i] == 0) continue;
    	연산자 개수 배열[i] -= 1;
    	/*다음 위치에 대해 재귀 호출*/
    	연산자 개수 배열[i] += 1;
}

 여기서 중요한 점은 마지막에 다시 연산자 개수를 +1 하는 부분입니다. 브루트 포스 문제는 모든 경우의 수를 독립적으로 탐색해야하기 때문에, 현재 위치에서 진행했던 것들을 다음 경우의 수를 탐색하기 전에 반드시 원상복구 해야합니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

int n, a[104], op[4], mx = -1e9, mn = 1e9;
int cal(int num1, int num2, int o){
    if(o == 0) return num1 + num2;
    else if(o == 1) return num1 - num2;
    else if(o == 2) return num1 * num2;
    else return num1 / num2;
}

void solve(int idx, int sum){
    if(idx == n){ //기저사례 : 모든 연산자 삽입 완료
        mx = max(mx, sum); mn = min(mn, sum);
        return;
    }
    /*현재 위치에 연산자 삽입*/
    for(int i = 0; i < 4; i++){
        if(op[i] == 0) continue;
        op[i]--;
        solve(idx + 1, cal(sum, a[idx], i));
        op[i]++;
    }
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    /*인덱스 순서대로 덧셈, 뺄셈, 곱셈, 나눗셈*/
    for(int i = 0; i < 4; i++) cin >> op[i];

    solve(1, a[0]);
    cout << mx << '\n' << mn;
    return 0;
}

 main 함수에서 처음 solve 함수를 호출하는 부분을 보면 첫번째 인자로 1, 두번째 인자로 a[0]을 전달하는 것을 볼 수 있습니다. 이는 계산식에서 가장 처음 나오는 수는 이미 더해졌다고 보고 그 다음 위치부터 탐색하는 것입니다.

 

 cal 함수는 두 개의 숫자를 전달받고 연산자 인덱스를 전달받아 연산 결과를 반환하는 함수입니다. 처음 연산자의 수를 입력 받을 때, 0부터 순서대로 덧셈, 뺄셈, 곱셈, 나눗셈으로 저장했기 때문에 인덱스 기반으로 함수를 구현했습니다.

---