[백준] 14888번, 연산자 끼워넣기 (Python)

문제

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

14888번: 연산자 끼워넣기

 

코드

import sys

n = int(input())
value = list(map(int, input().split()))
calc = list(map(int, input().split())) # +,-,*,//
maxx = -(sys.maxsize)
minn = sys.maxsize
sum = value[0]

def recursive(index, sum, plus,minus,mul,div):
    global maxx, minn

    # 정답을 찾은 경우
    if index == n:
        maxx = max(maxx, sum)
        minn = min(minn, sum)
        return

    # 불가능한 경우
    # 이 문제는 불가능한 경우가 없다.
    # 연산자가 n-1개 주어지고 연산자 넣는곳도 n-1개가 있기때문

    if plus > 0:
        recursive(index+1, sum+value[index],plus-1,minus,mul,div)
    if minus > 0:
        recursive(index+1, sum-value[index],plus,minus-1,mul,div)
    if mul > 0:
        recursive(index+1, sum*value[index],plus,minus,mul-1,div)
    if div > 0:
        if sum >= 0:
            recursive(index+1, sum//value[index],plus,minus,mul,div-1)
        else:
            recursive(index+1, -(-sum//value[index]),plus,minus,mul,div-1)
            
recursive(1,sum,calc[0],calc[1],calc[2],calc[3])
print(maxx)
print(minn)

 

값들은 받아서 value에 넣어주고 연산자는 calc에 넣어준다. 그리고 sum에 value[0]을 미리 넣어주고 index 1부터 재귀를 실행해준다.

 

연산자는 0보다 크다면 사용할 수있고 사용해주면 -1을 해준다.

 

나눗셈은 문제에서 정수 나눗셈으로 몫만 취하고 음수를 나눌경우에는 양수로 바꿔준다음에 몫을 음수로 바꿔줘서 계산해주라고 되어있다.

 

index가 n이랑 같으면 모든 값들 사이에 연산자를 넣어준 경우이다.

가장 큰값은 maxx에 저장해주고 가장 작은값은 minn에 저장해주면 된다.