[코드트리 조별과제][삼성 기출] 연산자 배치하기

[코드트리][삼성 기출] 연산자 배치하기

문제 링크

풀이

삼성 기출 문제입니다. 백트래킹 문제이나 요구 조건을 명확하게 구현하면 문제가 풀립니다.
기본적으로는 모든 +,-,*가 포함된 수식을 완전탐색하는 것으로 시작합니다.
대신 연산자마다 사용가능한 개수가 포함되어 있습니다.
떄문에 사용할 떄마다 여부를 체크하고 최종적으로 수식이 완성될 때
(즉, 최대 깊이까지 탐색했을 때) 그 값을 구하고 최대값,최솟값을 판별합니다.

코드

#include<bits/stdc++.h>

using int64 = long long;


constexpr int64 INF = 0xFFFFFFFFFFFFFF;
constexpr int64 MAX_N = 11;
constexpr int64 MAX_OP_COUNT = 3;

int64 num[MAX_N];
int64 op[MAX_OP_COUNT];

static inline int64 Max(int64 a, int64 b) { return a > b ? a : b; }
static inline int64 Min(int64 a, int64 b) { return a < b ? a : b; }

std::pair<int64, int64> dfs(int level, int target, int64 sum)
{
    if (level == target) return { sum,sum };

    std::pair<int64, int64> ret1, ret2, ret3;
    ret1 = ret2 = ret3 = { -INF,INF };

    if (op[0] > 0) {
        --op[0];
        ret1 = dfs(level + 1, target, sum + num[level]);
        ++op[0];
    }
    if (op[1] > 0) {
        --op[1];
        ret2 = dfs(level + 1, target, sum - num[level]);
        ++op[1];
    }
    if (op[2] > 0) {
        --op[2];
        ret3 = dfs(level + 1, target, sum * num[level]);
        ++op[2];
    }

    // 각 경우에서 최댓값과 최솟값을 구한다.
    return { Max(ret3.first,Max(ret1.first,ret2.first)), Min(ret3.second,Min(ret1.second,ret2.second)) };
}

int main(int argc, char** argv) {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);

    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i) std::cin >> num[i];
    for (int i = 0; i < MAX_OP_COUNT; ++i) std::cin >> op[i];

    std::pair<int64, int64> ans = dfs(1, N, num[0]);

    std::cout << ans.second << ' ' << ans.first;

    return EXIT_SUCCESS;
}