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

14888_연산자 끼워넣기 (Python)

0. 출처

• 유형 : 백트래킹 (silver 1)
• 링크 : 14888번: 연산자 끼워넣기

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

'''
1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

# 백트래킹 (Python3 통과, PyPy3도 통과)
import sys

N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3])

print(maximum)
print(minimum)

(4) 정리

(5) 참고

참고 풀이