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

Kimbab1004·2024년 6월 25일
0

Algorithm

목록 보기
38/102

간단한 백트래킹 문제였다. 숫자와 사칙연산을 저장하고 마지막 최댓값과 최솟값을 구하면 되는 문제이다.
그런데 위의 규칙만을 생각하고 문제를 풀면 위 처럼 처음에 오답이 나올 것이다.

그 이유는 최댓값은 상관 없지만 최솟값은 맨 처음 구한 값이 항상 최솟값이기 때문이다.
그렇기에 추가적으로 조건을 달아 입력한 숫자를 모두 사용했을때에만 최댓값과 최솟값을 구하게 변경하였다.

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int n;
int number[13];
int op[4];
int min_result = 1000000001;
int max_result = -1000000001;


void backtracking(int pos, int x) {
    if (x == n) {
        if (pos < min_result) min_result = pos;
        if (pos > max_result) max_result = pos;
    }
    else if (x < n) {

        for (int i = 0; i < 4; i++) {
            if (op[i] > 0 && i == 0) {
                    op[i] -= 1;
                    backtracking(pos + number[x], x + 1);
                    op[i] += 1;
            }
            if (op[i] > 0 && i == 1) {
                    op[i] -= 1;
                    backtracking(pos - number[x], x + 1);
                    op[i] += 1;
            }
            if (op[i] > 0 && i == 2) {
                    op[i] -= 1;
                    backtracking(pos * number[x], x + 1);
                    op[i] += 1;
            }
            if (op[i] > 0 && i == 3) {
                    op[i] -= 1;
                    backtracking(pos / number[x], x + 1);
                    op[i] += 1;
            }
        }
    }
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> number[i];
    }

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

    backtracking(number[0], 1);

    cout << max_result << "\n";
    cout << min_result;

    return 0;

}

0개의 댓글