백준 12101번 파이썬 문제풀이(1,2,3 더하기 2)

---

이 문제 역시 간단한 dfs + 백트래킹 문제이다. 단, 리스트에 연산자 N - 1 개를 집어놓고 백트래킹 조건에서 리스트에 있는 연산자를 꺼내면서 계산하는 방식은 python3 에서는 시간초과가 발생한다. 따라서 계산한 즉시 num 이라는 인자로 전달하는 방식을 사용하니 시간초과가 발생하지 않았다.

 

1. 인자로 계속해서 계산 결과를 전달하는 방식(시간초과x)

def dfs(depth, num):
    global max_
    global min_

    if depth == N - 1:

        if min_ > num:
            min_ = num
        if max_ < num:
            max_ = num
        return

    for i in range(len(oper)):
        if not visited[i]:
            visited[i] = True
            dfs(depth + 1, operation[oper[i]](num, nums[depth + 1]))
            visited[i] = False


operation = {
    '+': lambda x, y: x + y,
    '-': lambda x, y: x - y,
    'x': lambda x, y: x * y,
    '%': lambda x, y: x // y if x > 0 else -(abs(x) // y),

}
N = int(input())
arr = []
nums = list(map(int, input().split()))
temp = list(map(int, input().split()))
oper = []
for _ in range(temp[0]):
    oper.append('+')
for _ in range(temp[1]):
    oper.append('-')
for _ in range(temp[2]):
    oper.append('x')
for _ in range(temp[3]):
    oper.append('%')

max_ = -1e+20
min_ = 1e+20
visited = [False] * len(oper)
dfs(0, nums[0])
print(max_)
print(min_)

 

2. 리스트에 담아서 계산(파이썬에서는 시간초과, 파이파이 에서는 통과)

def dfs(depth):
    global max_
    global min_

    if depth == N - 1:
        temp = 0
        start = nums[0]
        for j in range(N - 1):
            temp = operation[arr[j]](start, nums[j + 1])
            start = temp

        if min_ > temp:
            min_ = temp
        if max_ < temp:
            max_ = temp
        return

    for i in range(len(oper)):
        if not visited[i]:
            visited[i] = True
            arr.append(oper[i])
            dfs(depth + 1)
            arr.pop()
            visited[i] = False


operation = {
    '+': lambda x, y: x + y,
    '-': lambda x, y: x - y,
    'x': lambda x, y: x * y,
    '%': lambda x, y: x // y if x > 0 else -(abs(x) // y),

}
N = int(input())
arr = []
nums = list(map(int, input().split()))
temp = list(map(int, input().split()))
oper = []
for _ in range(temp[0]):
    oper.append('+')
for _ in range(temp[1]):
    oper.append('-')
for _ in range(temp[2]):
    oper.append('x')
for _ in range(temp[3]):
    oper.append('%')

max_ = -1e+20
min_ = 1e+20
visited = [False] * len(oper)
dfs(0)
print(max_)
print(min_)