[Algorithm] 1일1솔 - 백준 14888 연산자 끼워넣기(python3)

문제링크

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

14888번: 연산자 끼워넣기

문제설명

N개로 이루어진 수열과 N-1개의 연산자가 주어질 때, 수식을 만들어 최댓값과 최솟값을 구하는 문제이다.

이 때 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 하며, 나눗셈은 정수 나눗셈으로 몫만 취한다.

또한, 음수를 양수로 나눌 때에는 양수로 바꾼 뒤 몫을 취한 후 그 몫을 음수로 바꾸어야 한다. 

예를 들어, -2 를 3으로 나누어야 한다면, -(-2) // 3 을 해준 후, -1을 곱해주어야 하는 식이다.

주어지는 N의 개수는 다음과 같이 2 이상 11 이하라는 범위 하에 주어지므로 시간 초과 문제는 크게 신경쓰지 않고 (python으로) dfs로 풀었다.

문제풀이

DFS를 기반으로 연산자에 따른 조건을 구분해주며 최대값과 최소값을 갱신해주었다. 연산 횟수를 저장하는 cur 변수를 설정해 연산이 한 번 이뤄질 때마다 +1 을 하였고, 그 수가 n 과 같아지는 때를 탈출조건으로 설정하였다.

계산되는 값의 변수는 ret로 설정했고, 계산은 앞에서부터 차례로 이뤄지므로 초기값은 피연산자로 주어지는 수들의 첫번째 값으로 두었다.

import sys
input = sys.stdin.readline

n = int(input())
opnd = list(map(int, input().split()))   # operand
optr = list(map(int, input().split()))   # opertor
max_val = -sys.maxsize  # 최대값 디폴트
min_val = sys.maxsize   # 최소값 디폴트

def dfs(cur, ret, p, m, mul, div):
    global min_val, max_val
    if cur == n:
        max_val = max(ret, max_val)
        min_val = min(ret, min_val)
        return

    if p:
        dfs(cur+1, ret+opnd[cur], p-1, m, mul, div)
    if m:
        dfs(cur+1, ret-opnd[cur], p, m-1, mul, div)
    if mul:
        dfs(cur+1, ret*opnd[cur], p, m, mul-1, div)
    if div:
        dfs(cur+1, -(abs(ret)//opnd[cur]) if ret < 0 else ret//opnd[cur], p, m, mul, div-1)

dfs(1, opnd[0], optr[0], optr[1], optr[2], optr[3])
print(max_val, min_val, sep='\n')


### 참고
print(-(2)//3)	# -1
print(-(2//3))	# 0