[알고리즘] 연산자 끼워넣기

포인트

• dfs 를 잘 이해하고 있는가?
• 연산자를 재귀적으로 계산에서 붙여놓자.

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

 c++/cpp

#include <iostream>

using namespace std;

int n;
int map[11];
int a, b, c, d;
int target, maxValue, minValue;

void dfs(int index, int cnt, int plus, int minus, int multiple, int divide, int sum) {
    if (cnt == target) {
        maxValue = max(maxValue, sum);
        minValue = min(minValue, sum);
        return;
    }

    if (plus < a)
        dfs(index + 1, cnt + 1, plus + 1, minus, multiple, divide, sum + map[index]);
    if (minus < b)
        dfs(index + 1, cnt + 1, plus, minus + 1, multiple, divide, sum - map[index]);
    if (multiple < c)
        dfs(index + 1, cnt + 1, plus, minus, multiple + 1, divide, sum * map[index]);
    if (divide < d)
        dfs(index + 1, cnt + 1, plus, minus, multiple, divide + 1, sum / map[index]);
}

int main() {
    maxValue = -987654321;
    minValue = 987654321;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> map[i];

    cin >> a >> b >> c >> d;
    target = n - 1;

    dfs(1, 0, 0, 0, 0, 0, map[0]);
    cout << maxValue << endl
         << minValue << endl;
}

 

python

import sys

sys.stdin = open('input.txt')

n = int(input())
data = list(map(int, input().split()))
a, b, c, d = list(map(int, input().split()))

min_value = 987654321
max_value = -97654321


def go(plus, minus, mul, div, cnt, summation): # 재귀
	global max_value
	global min_value
	
	if cnt == n:
		max_value = int(max(max_value, summation))
		min_value = int(min(min_value, summation))
		return
	
	if plus > 0:
		go(plus - 1, minus, mul, div, cnt + 1, summation + data[cnt])
	if minus > 0:
		go(plus, minus - 1, mul, div, cnt + 1, summation - data[cnt])
	if mul > 0:
		go(plus, minus, mul - 1, div, cnt + 1, summation * data[cnt])
	if div > 0:
		if summation < 0:
			go(plus, minus, mul, div - 1, cnt + 1, -((-summation) // data[cnt]))
		else:
			go(plus, minus, mul, div - 1, cnt + 1, summation // data[cnt])


go(a, b, c, d, 1, data[0])
print(max_value)
print(min_value)