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

문제

 

---

풀이

 

숫자의 순서는 고정되어 있으니 백트래킹의 대상이 되는 것은 사칙연산 기호 뿐이다.

종료 조건을 만나면 함수를 종료하던 이전 문제들과 달리 노드의 끝에 다다르면 최댓값, 최솟값을 갱신하며 모든 경우의 수를 따져야 한다.

---

소스코드

 

#include <iostream>
using namespace std;

int min_num = 1000000000;
int max_num = -1000000000;
int arr[11];
int op[4];
int N;

int cal(int a, int b, int op) { //계산
    int result = 0;
    switch (op) {
        case 0:
            result = a + b;
            break;
        case 1:
            result = a - b;
            break;
        case 2:
            result = a * b;
            break;
        case 3:
            result = a / b;
            break;
    }
    return result;
}

void put_operator(int result, int index) {
    if (index == N - 1) { //노드 맨 아래까지 탐색하면 결과 비교
        if (result > max_num)
            max_num = result;
        if (result < min_num)
            min_num = result;
    }
    for (int i = 0; i < 4; i++) {
        if (op[i] != 0) {
            op[i]--; //아래로 내려감
            put_operator(cal(result, arr[index + 1], i), index + 1);
            op[i]++; //위로 다시 올라감
        }
    }
}

int main() {
    int i;

    cin >> N;
    for (i = 0; i < N; i++)
        cin >> arr[i];
    for (i = 0; i < 4; i++)
        cin >> op[i];
    put_operator(arr[0], 0);
    cout << max_num << '\n' << min_num;
}

전체 소스코드이다.

 

int min_num = 1000000000;
int max_num = -1000000000;
int arr[11];
int op[4];
int N;

숫자를 저장할 arr배열과 연산기호를 저장할 op배열 그리고 최댓값과 최솟값을 저장할 min_num, max_num 변수를 준비한다.

 

void put_operator(int result, int index) {
    if (index == N - 1) { //노드 맨 아래까지 탐색하면 결과 비교
        if (result > max_num)
            max_num = result;
        if (result < min_num)
            min_num = result;
    }
    for (int i = 0; i < 4; i++) {
        if (op[i] != 0) {
            op[i]--; //아래로 내려감
            put_operator(cal(result, arr[index + 1], i), index + 1);
            op[i]++; //위로 다시 올라감
        }
    }
}

함수의 종료조건이 index == N이 아니라 index == N - 1이라 의문을 품을 수도 있는데,

숫자의 개수 기준이 아니라 연산자의 개수 기준이라서 그렇다.

아무튼 노드 맨 아래까지 탐색을 마치면 그 계산 결과인 result 값을 현재까지의 최댓값, 최솟값과 비교해 갱신여부를 결정한다.

 

a (op) b를 계산한다고 할 때, 기존에 result 변수로 넘어온 값이 a가 되고 a의 다음 수(arr[index + 1])이 b가 되며 이 둘의 계산에 사용할 op는 op[i]가 된다. 백트래킹은 당연히 되돌아갈 곳이 있어야 하기 때문에 put_operator 호출 이후에 op[i]++를 해준다.

 

int cal(int a, int b, int op) { //계산
    int result = 0;
    switch (op) {
        case 0:
            result = a + b;
            break;
        case 1:
            result = a - b;
            break;
        case 2:
            result = a * b;
            break;
        case 3:
            result = a / b;
            break;
    }
    return result;
}

cal 함수는 이렇게 간단하게 생겼기 때문에 인자만 잘 넘겨줬다면 계산한 결과를 잘 넘겨줄 것이다.