14888번: 연산자 끼워넣기

14888번: 연산자 끼워넣기

사용 언어: C++

 

문제 요약

• N개의 수와 N-1개의 연산자가 주어짐.
• 수의 순서를 바꾸지 않고, 주어진 연산자를 모두 사용해 수식을 완성.
• 연산 순서는 앞에서부터(왼쪽에서 오른쪽으로) 진행.
• 가능한 모든 수식 결과 중 최댓값과 최솟값을 출력해야 함.

---

풀이

• 가능한 연산자 순열을 모두 탐색해야 하므로 백트래킹(DFS) 을 사용.
• 각 재귀 단계마다 남아 있는 연산자 중 하나를 선택해 현재까지의 계산 결과를 갱신.
• 나눗셈은 음수 처리를 주의해야 함 (C++ 기준: -(-a / b) 방식으로 처리).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<int> A;
int op[4]; // +, -, *, /
int max_val = -1e9;
int min_val = 1e9;

void dfs(int idx, int val) {
    if (idx == N) {
        max_val = max(max_val, val);
        min_val = min(min_val, val);
        return;
    }

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

            int next = val;
            if (i == 0) next += A[idx];
            else if (i == 1) next -= A[idx];
            else if (i == 2) next *= A[idx];
            else if (i == 3) {
                if (val < 0)
                    next = -(-val / A[idx]);
                else
                    next = val / A[idx];
            }

            dfs(idx + 1, next);
            op[i]++; // backtrack
        }
    }
}

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

    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; i++)
        cin >> A[i];
    for (int i = 0; i < 4; i++)
        cin >> op[i];

    dfs(1, A[0]);

    cout << max_val << '\n' << min_val << '\n';
    return 0;
}