[백준 14888] 연산자 끼워넣기

문제 보기

이 문제는 브루트 포스 문제이다.

N개의 수로 이루어진 수열에서, 각 숫자 사이에 사칙연산자 +, -, *, / 를 집어넣어서 최대, 최소값을 구하는 문제이다.

Iterative한 방법은 실력이 부족해서 구현하지 못했다..

이 문제를 풀면서 깨달은 점은, 파이썬에서 음수의 나눗셈을 할 때 신경을 써야한다는 것이다.

print(-3 / 4)
print(int(-3 / 4))
print(-3 // 4)

이 값들의 결과값은 다음과 같다.

문제를 풀면서 파이썬에서 나누기연산은 부호에 관계없이 모두 floor division을 한다는 것을 알았다.

따라서 문제에서 요구하는 올바른 몫을 구하기 위해서는 결과값에서 int형으로 캐스팅해서 몫을 구해야한다.

import sys
 
n = int(sys.stdin.readline())
num_list = list(map(int, sys.stdin.readline().split()))
a, b, c, d = map(int, sys.stdin.readline().split())
max_num, min_num = -sys.maxsize + 1, sys.maxsize
 
 
def solution(num, i, add, minus, multiply, divide):
    global n, max_num, min_num
    if i == n:
        max_num = max(max_num, num)
        min_num = min(min_num, num)
        return
    else:
        if add:
            solution(num + num_list[i], i + 1, add - 1, minus, multiply, divide)
        if minus:
            solution(num - num_list[i], i + 1, add, minus - 1, multiply, divide)
        if multiply:
            solution(num * num_list[i], i + 1, add, minus, multiply - 1, divide)
        if divide:
            solution(int(num / num_list[i]), i + 1, add, minus, multiply, divide - 1)
 
 
solution(num_list[0], 1, a, b, c, d)
print(max_num)
print(min_num)