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

문제

 

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

14888번: 연산자 끼워넣기

---

Algorithm

N개의 수와 그 사이사이에 들어갈 N-1개의 연산자가 주어지면 연산자를 적절히 배치하여 계산한 결과의 최대, 최소를 찾는 문제이다. 연산의 순서는 단순하게 연산자 우선순위를 무시하고 앞에서 부터 진행하면 되고, 음수를 나눌때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾸면 된다고 문제에서 제시했다.

N의 범위가 2이상 11 이하이므로 재귀함수로 백트래킹할수 있겠다 생각했다.재귀함수를 보면, 현재 몇번의 계산을 했는지 나타내는 cur, 지금까지 계산한 결과가 있는 ans를 선언하고, cur이 N-1일때 결과값을 리턴해주면 된다고 생각했다.

for문을 돌려주는데, 연산자의 개수를 받는 배열 Operator의 변수가 0이면 continue를 해주어 제외시켜주고, 그 이외의 것을 선택했다면 Operator의 i번째 값을 -1해주고, i의 값에따라 덧셈, 뺄셈, 곱셈, 나눗셈을 해준 값을 다시 재귀함수에 넣어주고, ans에도 결과값을 반영시켜준다.재귀함수에서 cur이 N-1이 되면, 최대 최소값과 비교하여 반영시켜주고, 최종적으로 최대, 최소의 순으로 출력해주면 된다.

이 코드 그대로 #15658 연산자 끼워넣기(2)에 넣어도 성공이 된다!

---

 

 

Code

input = __import__('sys').stdin.readline
from itertools import combinations
import math

n = int(input())
nums= list(map(int,input().split())) 
Operators = list(map(int,input().split()))
answers = [1000000000,-1000000000]
def recur(cur,ans):
    if cur == n-1:
        if answers[1] < ans:
            answers[1] = ans
        if answers[0] > ans:
            answers[0] = ans
        return

    for i in range(4):
        if Operators[i] < 1:
            continue

        Operators[i] -= 1
        if i == 0:
            recur(cur + 1, ans + nums[cur + 1])
        elif i == 1:
            recur(cur + 1, ans - nums[cur + 1])
        elif i == 2:
            recur(cur + 1, ans * nums[cur + 1])
        else:
            if ans < 0 :
                recur(cur + 1, (abs(ans) // nums[cur + 1])*-1)
            else:
                recur(cur + 1, ans // nums[cur + 1])
        Operators[i] += 1

recur(0,nums[0])

print(answers[1])
print(answers[0])