[C++] 백준/BOJ - 14888 : 연산자 끼워넣기 (백트래킹 방식)

문제 이해 단계

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

N개의 수와 N-1개의 연산자가 주어진다.
연산자가 주어지는 방법은 공백을 구분으로 개수로 들어온다.

처음부터 덧셈, 뺄셈, 곱셈, 나눗셈이다.
나눗셈은 몫만 남고 나머지는 버린다.

N개의 수 사이에 입력받은 연산자들을 마음대로 배열할 수 있을 때,
나올 수 있는 최댓값과 최솟값을 구하는 문제

 

---

문제 접근 단계

해당 문제에서 봐야 할 점은 수의 개수인 N이 최대 11개라는 것이다.
이에 따라 연산자도 최대 10개밖에 되지 않는다.

모든 연산을 하나하나 확인하면 O(n)이 n! 가 될 것인데,
11! 이기 때문에 충분히 가능하다.

하지만 사이사이에 연산자들을 차례차례 나열해 보고
계산 값의 최댓값의 최솟값을 구하는 백트래킹 방식을 사용해 보겠다.

이는 단순한 백트래킹 연습이며 학습 목적이다.

---

입력된 연산자 백트래킹하기 쉽게 만들기

백트래킹 해야 하는 것은 연산자들이다.

그런데 연산자들이 위치와 개수대로 정리되어 있어서 백트래킹하기에는 좀 복잡하다.
그래서 이를 백트래킹하기 쉽도록 하나하나씩 펼쳐 나열할 것이다.

각각의 key-value 느낌으로

1- 덧셈
2- 뺄셈
3- 곱셈
4- 나눗셈

매핑해 두고 각 개수만큼 해당 번호의 원소를 만들 것이다.

예를 들어 2 1 3 0이라면 11/2/333/0 이런 식으로
입력을 하나하나씩 받아 백트래킹하기 쉽도록 만들었다.

 

---

백트래킹

이제 백트래킹을 할 때, 신경 써야 할 점을 쓸 점을 서술해 보겠다.

우선 주어진 수의 순서가 바뀌어선 안되기 때문에
재귀를 호출할 때 바뀌지 않도록 주의해야 한다.

사실 백트래킹은 말로 하는 설명보다는
코드로 보는 것이 빠르기 때문에 빠르게 코드로 살펴보자.

 

---

문제 구현 단계

int cal(int a,int b, int idx){
    switch(idx){
        case 1 : return a+b;
        case 2 : return a-b;
        case 3 : return a*b;
        case 4 : return a/b;
    }
    return 0;
}

// 백트래킹
void backTracking(vector<int> list,int cnt, int idx){
	// 마지막 인덱스를 지났을 때 결과와 최댓값과 최솟값을 비교
    if(idx >= N){
        maxAns = max(maxAns,cnt);
        minAns = min(minAns,cnt);
        return;
    }
	
    
    for(int j = 0; j < list.size(); j++){
    	// 이미 사용했던 연산자나 0으로 들어온 연산자는 제외
        if(v[j] || list[j] == 0) continue;
        int val = cal(cnt,numbers[idx],list[j]);
        v[j] = true; // 사용 처리
        backTracking(list,val,idx+1);
        v[j] = false; // 다른 호출 때 사용할 수 있도록 사용 처리 해제
    }
}

백트래킹 함수인데 매개변수로 연산자 리스트와,
현재 계산 값 cnt, 그리고 현재 탐색하고 있는 번호 인덱스인 idx가 들어온다.

중복 사용을 방지하기 위해서, v 배열을 두어 방문 체크를 한다.

그리고 해당 재귀함수 사용이 끝났을 때,다른 재귀함수에서 사용할 수 있도록
사용처리 한 것을 해제해줘야 한다.

마지막으로 idx가 N과 같다는 것은
수 배열 끝까지 왔다는 뜻이므로 지금까지 계산한 값과 최솟값, 최댓값을 비교한다.

그리고 위에 있는 cal 함수는
인덱스를 받아 연산으로 바꿔주는 역할이다.

이제 아래에 전체 코드를 올리고 끝내겠다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int N;
int numbers[12];
int maxAns = INT32_MIN;
int minAns = INT32_MAX;
bool v[12] = {false,};

int cal(int a,int b, int idx){
    switch(idx){
        case 1 : return a+b;
        case 2 : return a-b;
        case 3 : return a*b;
        case 4 : return a/b;
    }
    return 0;
}
void backTracking(vector<int> list, int cnt, int idx){
    if(idx >= N){
        maxAns = max(maxAns,cnt);
        minAns = min(minAns,cnt);
        return;
    }

    for(int j = 0; j < list.size(); j++){
        if(v[j] || list[j] == 0) continue;
        int val = cal(cnt,numbers[idx],list[j]);
        v[j] = true;
        backTracking(list,val,idx+1);
        v[j] = false;
    }
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> N;
    for(int i = 0; i < N; i++) cin >> numbers[i];

    vector<int> list;
    for(int i = 0; i < 4; i++) {
        int idx;
        cin >> idx;
        if(idx == 0) list.push_back(0);
        for(int j = 0; j < idx; j++) list.push_back(i+1);
    }

    backTracking(list,numbers[0],1);
    
    cout << maxAns << "\n";
    cout << minAns;
}

 

---

시행착오

백트래킹 문제를 많이 풀어봤음에도 불구하고,
구현하는 것은 역시 어려운 것 같다.

풀이는 간단해 보이지만 한 3~4시간 걸려서 푼 것이다.

친구가 1시간 걸려서 못 풀면 그냥 답지 보랬는데..
근데 진짜 풀 수 있을 것 같아서 ㅎㅎ..