백준 알고리즘 14888 (연산자 끼워넣기) - python (재풀이)

백준 알고리즘 14888 (연산자 끼워넣기) - python

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

14888번: 연산자 끼워넣기

 

 

백트래킹의 컨셉에 충실!

식의 계산은 앞에서부터 진행! 계산을 하면서 

각 연산자 count를 -1 -> dfs 진행 -> 다시 count +1

 

[문제 풀이]

1. 탈출 조건 : depth == N

   _max와 _min을 global로 이용하여 저장

2. result를 dfs에서 계속 넘겨주며 계산

3. 연산자(calc) count를 이용하여 +, -, *, /일 때를 구분

4. 연산자 count를 -1 

5. result 계산

6. 연산자 count를 +1하여 백트래킹

 

import sys
N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
# + - * int(/)
calc = list(map(int, sys.stdin.readline().split()))
_max = -1e9
_min = 1e9

def dfs(depth, result):
    global _max, _min
    if depth == N:
        _max = max(result, _max)
        _min = min(result, _min)
        return
    if calc[0]:  # plus
        calc[0] -= 1
        dfs(depth + 1, result + nums[depth])
        calc[0] += 1
    if calc[1]:  # minus
        calc[1] -= 1
        dfs(depth + 1, result - nums[depth])
        calc[1] += 1
    if calc[2]:  # mul
        calc[2] -= 1
        dfs(depth + 1, result * nums[depth])
        calc[2] += 1
    if calc[3]:  # div
        calc[3] -= 1
        dfs(depth + 1, int(result / nums[depth]))
        calc[3] += 1
    return

dfs(1, nums[0])
print(_max)
print(_min)