백준_15658_연산자 끼워넣기(2)

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

15658번: 연산자 끼워넣기 (2)

 

문제요약)

N개의 수로 이루어진 수열, 연산자기 주어지는데 연산자의 개수는 N - 1보다 많을 수도 있다.

수와 수 사이에 연산자를 하나씩 넣어서, 수식을 만들 수 있다. 단, 주어진 수의 순서는 바꾸지 못한다.

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행한다. 

나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준에 따라 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수로 바꾼다.

만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하라

 

입력)

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

 

출력)

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

풀이포인트)

백준_14888_연산자 끼워넣기 처러 DFS의 백트래킹 풀이가 가능하다. 

백준_14888_연산자 끼워넣기

연산자 끼워넣기(2) 풀이는 변수로 변하는 모든 변수를 넘겨준다. 

핵심은 주어진 숫자와 연산자로 조합할 수 있는 모든 경우의 수를 따져야 함.

 

풀이)

n = int(input()) #수의 개수 입력 받기
num = list(map(int, input().split())) #숫자 입력받기
plus, minus, mul, div = map(int, input().split()) #연산자 입력받기

#최대, 최소 범위 (-10억 to 10억)
myMAX = -int(1e9)
myMin = int(1e9)

#dfs
def dfs(index, result, plus, minus, mul, div): #()안을 매개변수들로 가지는 dfs 함수
    global myMAX, myMin #전역변수 설정
    if index == n: #수의 개수와 일치 할 때
        #최대, 최솟값
        myMAX = max(myMAX, result)
        myMin = min(myMin, result)
        return
    if plus > 0: #+계수가 0보다 크면
        dfs(index + 1, result + num[index], plus - 1, minus, mul, div)
    if minus > 0: #-계수가 0보다 크면
        dfs(index + 1, result - num[index], plus, minus - 1, mul, div)
    if mul > 0: #*계수가 0보다 크면
        dfs(index + 1, result * num[index], plus, minus, mul - 1, div)
    if div > 0: #/계수가 0보다 크면
        dfs(index + 1, int(result//num[index]), plus, minus, mul, div - 1)

#결과
dfs(1, num[0], plus, minus, mul, div)
print(myMAX)
print(myMin)