백준 알고리즘 14888 (연산자 끼워넣기) - C++, Python

[문제] 백준 알고리즘 14888 (연산자 끼워넣기)

> https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

N개의 숫자가 들어있는 수열 사이에 N-1개의 연산자를 끼워넣어 최소/최대값을 찾는 문제.

연산 순서는 앞에서부터 차례대로 계산한다. 그나마 편한 조건.

연산자는 +, -, *, / 순으로 갯수가 주어지고, 브루트포스이면서 백트래킹 개념의 문제이다.

 

 

[문제 해결]

 

1. 맨 앞 숫자와 연산자 갯수를 시작으로 DFS를 진행한다.

2. depth를 기준으로 n개가 만족되면, 최댓값 또는 최솟값을 구한다.

3. 모든 연산자를 진행할 텐데, 각 연산자의 값이 0이 아니면 아래와 같이 재귀시킨다.

4. 계산 값, 깊이 +1, 실행한 연산자의 값 -1, 나머지 연산자 값을 재귀시킨다.

    - C++이 아닌 경우(여기선 Python)는 나눗셈 방식에서 -(-나눗셈)을 해준다.)

5. 최댓값, 최솟값을 출력한다.  

 

 

[C++]

#include <cstdio>
using namespace std;

const int INF = 1e9;
int n, result, _min = INF, _max = -INF;
int nums[11], oper[4];

int solve_dfs(int depth, int result,int add, int sub, int mul, int div) {
	if (depth == n) {
		if (_max < result) _max = result;
		if (_min > result) _min = result;
		return 0;
	}
	if (add) solve_dfs(depth + 1, result + nums[depth], add - 1, sub, mul, div);
	if (sub) solve_dfs(depth + 1, result - nums[depth], add, sub - 1, mul, div);
	if (mul) solve_dfs(depth + 1, result * nums[depth], add , sub, mul - 1, div);
	if (div) solve_dfs(depth + 1, result / nums[depth], add, sub, mul, div - 1);
	return 0;
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &nums[i]);
	for (int i = 0; i < 4; i++) scanf("%d", &oper[i]);
	result = nums[0];
	solve_dfs(1, result, oper[0], oper[1], oper[2], oper[3]);
	printf("%d\n", _max);
	printf("%d\n", _min);
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
n = int(input())
_min = 1e9
_max = -1e9
nums = list(map(int, input().split()))
oper = list(map(int, input().split()))

def solve_dfs(depth, result, add, sub, mul, div):
    global _max, _min
    if depth == n:
        _max = max(_max, result)
        _min = min(_min, result)
        return
    if add:
        solve_dfs(depth + 1, result + nums[depth], add - 1, sub, mul, div)
    if sub:
        solve_dfs(depth + 1, result - nums[depth], add, sub - 1, mul, div)
    if mul:
        solve_dfs(depth + 1, result * nums[depth], add, sub, mul - 1, div)
    if div:
        div_result = result // nums[depth] if result > 0 else -(-result // nums[depth])
        solve_dfs(depth + 1, div_result, add, sub, mul, div - 1)
    return

result = nums[0]
solve_dfs(1, result, oper[0], oper[1], oper[2], oper[3])
print(_max, _min)