[백준/Python] #14888번 연산자 끼워넣기

문제 

• N개의 수로 이루어진 수열 A1, A2, ..., AN과 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로 이루어진 연산자 N-1개를 조합하여 만들 수 있는 식 중 결과가 최대인 것과 최소인 것 출력하기(단, 연산자 우선순위는 무시하고 앞에서부터 계산) 
• 나눗셈은 정수 나눗셈으로 몫만 취하고, 음수를 양수를 나눌 때는 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수로 바꾼다. 

 

해결 방법

 

1. 순열로 풀이: permutation을 사용해 연산자의 모든 순열을 구하고 계산한 뒤 최대값, 최소값 출력 → 많은 시간 소요

2. 백트래킹으로 풀이: 재귀로 계속해서 타고 들어가며 모든 연산을 수행하고, 연산이 끝난 식은 현재까지의 최대값, 최소값과 비교해서 업데이트 → 시간, 공간 효율 더 좋음 

나눗셈 연산은 int(total/Arr[depth])로 처리해야 문제의 조건을 만족할 수 있는데 양수일 때는 total//Arr[depth]로도 같은 값이 나오지만 음수의 경우에는 더 작은 정수로 내림을 하기 때문에 -5 // 2와 같은 연산에서는 -2.5를 내림한 -3이 정답으로 나오게 된다. 따라서 나눗셈 연산 후 소수점 이하를 버리는 int로 계산해야 한다. 

 

정답

백트래킹으로 풀이 

import sys 
input = sys.stdin.readline
from itertools import permutations

def cal(depth, total, plus, minus, multiply, divide):
    global max_val, min_val
    
    if depth == N:
        max_val = max(max_val, total)
        min_val = min(min_val, total)
        return
    
    if plus:
        cal(depth+1, total+Arr[depth], plus-1, minus, multiply, divide)
    if minus:
        cal(depth+1, total-Arr[depth], plus, minus-1, multiply, divide)
    if multiply:
        cal(depth+1, total*Arr[depth], plus, minus, multiply-1, divide)
    if divide:
        cal(depth+1, int(total/Arr[depth]), plus, minus, multiply, divide-1)
    
                
if __name__ == "__main__" : 
    N = int(input())
    Arr = list(map(int, input().split()))
    Operator = list(map(int, input().split()))
    
    max_val, min_val = float('-inf'), float('inf')
    cal(1, Arr[0], Operator[0], Operator[1], Operator[2], Operator[3])
    
    print(max_val)
    print(min_val)

 

순열로 풀이

import sys 
input = sys.stdin.readline
from itertools import permutations

def create_target(Ns):
    tmp = []
    for i in range(4):
        target = ''
        if i == 0:
            target = '+'
        elif i == 1:
            target = '-'
        elif i == 2:
            target = 'x'
        else:
            target = '/'
        for _ in range(Ns[i]):
            tmp.append(target)
    return tmp

def cal(t):
    s = Arr[0]
    for i in range(len(t)):
        if t[i] == '+':
            s += Arr[i+1]
        elif t[i] == '-':
            s -= Arr[i+1]
        elif t[i] == 'x':
            s *= Arr[i+1]
        else:
            if s < 0:
                s *= -1
                s //= Arr[i+1]
                s *= -1
            else:
                s //= Arr[i+1]
    return s
                
if __name__ == "__main__" : 
    N = int(input())
    Arr = list(map(int, input().split()))
    Operator = list(map(int, input().split()))
    
    tlist = list(permutations(create_target(Operator), N-1))
    sum_list = []
    for t in tlist:
        sum_list.append(cal(t))
    
    print(max(sum_list))
    print(min(sum_list))