14888번: 연산자 끼워넣기

문제링크

C++

#include <iostream>

using namespace std;

int N;

int A[11];
int oper[4];

int min_ret = 1000000000;
int max_ret = -1000000000;

void fun(int idx, int ret, int add, int sub, int mult, int div){
    if (idx == N){
        if (ret < min_ret)
            min_ret = ret;
        if (ret > max_ret)
            max_ret = ret;
        return ;
    }
    if (add > 0)
        fun(idx + 1, ret + A[idx], add - 1, sub, mult, div);
    if (sub > 0)
        fun(idx + 1, ret - A[idx], add, sub - 1, mult, div);
    if (mult > 0)
        fun(idx + 1, ret * A[idx], add, sub, mult - 1, div);
    if (div > 0 && A[idx] != 0){
        fun(idx + 1, ret / A[idx], add, sub, mult, div - 1);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> A[i];
    }
    for (int i = 0; i < 4; i++){
        cin >> oper[i];
    }
    fun(1, A[0], oper[0], oper[1], oper[2], oper[3]);
    cout << max_ret << "\n" << min_ret << "\n";
}

Python

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
num_oper = list(map(int, input().split()))

A_len = len(A)

min_ret = 10000000000
max_ret = -10000000000

def fun(idx, ret, num_add, num_sub, num_mult, num_div):
    global A, A_len, min_ret, max_ret
    if idx == A_len:
        if ret < min_ret:
            min_ret = ret
        if ret > max_ret:
            max_ret = ret
        return
    if num_add > 0:
        fun(idx + 1, ret + A[idx], num_add - 1, num_sub, num_mult, num_div)
    if num_sub > 0:
        fun(idx + 1, ret - A[idx], num_add, num_sub - 1, num_mult, num_div)
    if num_mult > 0:
        fun(idx + 1, ret * A[idx], num_add, num_sub, num_mult - 1, num_div)
    if num_div > 0 and A[idx] != 0:
        if ret >= 0:
            fun(idx + 1, ret // A[idx], num_add, num_sub, num_mult, num_div - 1)
        else:
            fun(idx + 1, -((-ret) // A[idx]), num_add, num_sub, num_mult, num_div - 1)

fun(1, A[0], num_oper[0], num_oper[1], num_oper[2], num_oper[3])

print(max_ret)
print(min_ret)

• 재귀 + 브루트포스
• $O(4^N)$
• 음수에서 파이썬에서 버림 나눗셈은 cpp의 나눗셈과 결과가 다를 수 있음에 주의(나머지가 없는 경우는 동일하므로 무조건 1 더하면 안 됨. 그렇게 했다가 계속 틀림)