January 5, 2023

문제 요약

• N개의 수로 이루어진 수열과 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷) 연산자의 수가 주어졌을 때 만들 수 있는 최댓값과 최솟값 출력
• 2 ≤ N ≤ 11
• 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
• 시간 제한 : 2초

문제 풀이

import sys
import math

input()

number_list = list(map(int, input().split()))
op_list = list(map(int, input().split()))

def calc_min(plus_cnt, minus_cnt, multiply_cnt, divide_cnt, idx, result):
    min = sys.maxsize
    if (idx == len(number_list)):
        return result

    if (plus_cnt):
        compare = calc_min(plus_cnt - 1, minus_cnt, multiply_cnt, divide_cnt, idx + 1, result + number_list[idx])
        min = compare if min > compare else min
    if (minus_cnt):
        compare = calc_min(plus_cnt, minus_cnt - 1, multiply_cnt, divide_cnt, idx + 1, result - number_list[idx])
        min = compare if min > compare else min
    if (multiply_cnt):
        compare = calc_min(plus_cnt, minus_cnt, multiply_cnt - 1, divide_cnt, idx + 1, result * number_list[idx])
        min = compare if min > compare else min
    if (divide_cnt):
        sign = 1 if result > 0 else -1
        compare = calc_min(plus_cnt, minus_cnt, multiply_cnt, divide_cnt - 1, idx + 1, sign * (abs(result) // number_list[idx]))
        min = compare if min > compare else min
    
    return min

def calc_max(plus_cnt, minus_cnt, multiply_cnt, divide_cnt, idx, result):
    max = -sys.maxsize + 1
    if (idx == len(number_list)):
        return result

    if (plus_cnt):
        compare = calc_max(plus_cnt - 1, minus_cnt, multiply_cnt, divide_cnt, idx + 1, result + number_list[idx])
        max = compare if max < compare else max
    if (minus_cnt):
        compare = calc_max(plus_cnt, minus_cnt - 1, multiply_cnt, divide_cnt, idx + 1, result - number_list[idx])
        max = compare if max < compare else max
    if (multiply_cnt):
        compare = calc_max(plus_cnt, minus_cnt, multiply_cnt - 1, divide_cnt, idx + 1, result * number_list[idx])
        max = compare if max < compare else max
    if (divide_cnt):
        sign = 1 if result > 0 else -1
        compare = calc_max(plus_cnt, minus_cnt, multiply_cnt, divide_cnt - 1, idx + 1,  sign * (abs(result) // number_list[idx]))
        max = compare if max < compare else max
    
    return max

print(calc_max(op_list[0], op_list[1], op_list[2], op_list[3], 1, number_list[0]))
print(calc_min(op_list[0], op_list[1], op_list[2], op_list[3], 1, number_list[0]))

• 재귀 호출을 통해 완전 탐색 진행
• 두 개의 함수를 합치고, 전역 변수로 선언하면 더 빠르고 간단하게 개선 가능