174. 연산자 끼워 넣기

백준

1. DFS

중복 순열(product) 라이브러리

• 예를 들어 n = 4라고 하면, 사칙 연산 중에서 중복을 허용하여 3개를 뽑아 나열하는 모든 경우를 고려해야 한다.

from itertools import product

n = 4
print(list(product(['+','-','*','/'], reapeat = (n - 1)))

n = int(input())
data = list(map(int, input().split()))

add, sub, mul, div = map(int, input().split())

#최솟값, 최댓값 초기화
min_value = 1e9
max_value = -1e9

def dfs(i, now): 
  global min_value, max_value, add, sub, mul, div

  #모든 연산자 다 사용한 경우, 최솟값과 최댓값 업데이트
  if i == n:
    min_value = min(min_value, now)
    max_value = max(max_value, now)

  else:
    #각 연산에 대해 재귀적으로 수행
    if add > 0:
      add -= 1
      dfs(i + 1, now + data[i])
      add += 1

    if sub > 0:
      sub -= 1
      dfs(i + 1, now - data[i])
      sub += 1

    if mul > 0:
      mul -= 1
      dfs(i + 1, now * data[i])
      mul += 1
    
    if div > 0:
      div -= 1
      dfs(i + 1, int(now / data[i])) #나눌 땐 나머지 제거
      div += 1

#연산자는 숫자의 개수보다 1 적으니 1부터
dfs(1, data[0])

print(max_value)
print(min_value)

2. C++

#include <bits/stdc++.h>

using namespace std;

int n;
// 연산을 수행하고자 하는 수 리스트
vector<int> arr;
// 더하기, 빼기, 곱하기, 나누기 연산자 개수
int add, sub, mul, divi;

// 최솟값과 최댓값 초기화
int minValue = 1e9;
int maxValue = -1e9;

// 깊이 우선 탐색 (DFS) 메서드
void dfs(int i, int now) {
    // 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
    if (i == n) {
        minValue = min(minValue, now);
        maxValue = max(maxValue, now);
    }
    else {
        // 각 연산자에 대하여 재귀적으로 수행
        if (add > 0) {
            add -= 1;
            dfs(i + 1, now + arr[i]);
            add += 1;
        }
        if (sub > 0) {
            sub -= 1;
            dfs(i + 1, now - arr[i]);
            sub += 1;
        }
        if (mul > 0) {
            mul -= 1;
            dfs(i + 1, now * arr[i]);
            mul += 1;
        }
        if (divi > 0) {
            divi -= 1;
            dfs(i + 1, now / arr[i]);
            divi += 1;
        }
    }
}

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }
    cin >> add >> sub >> mul >> divi;

    // DFS 메서드 호출
    dfs(1, arr[0]);

    // 최댓값과 최솟값 차례대로 출력
    cout << maxValue << '\n' << minValue << '\n';
}