BOJ 15658 - 연산자 끼워넣기 (2) (Python)

S2, 백트래킹

풀이

처음엔 permutation을 통해 전체 연산자 중 n-1개를 뽑으려 했지만
시간초과가 나 실패했다.

• 백트래킹을 통해 총 연산자의 수가 n-1개가 될 때까지 반복하며 진행

from sys import stdin

n = int(stdin.readline())
nums = list(map(int, stdin.readline().split()))
op = list(map(int, stdin.readline().split()))

maxRes = -int(1e9)
minRes = int(1e9)

def dfs(idx, now):
    global maxRes, minRes

    if idx == n:
        maxRes = max(maxRes, now)
        minRes = min(minRes, now)
        return

    if op[0] > 0:
        op[0] -= 1
        dfs(idx + 1, now + nums[idx])
        op[0] += 1

    if op[1] > 0:
        op[1] -= 1
        dfs(idx + 1, now - nums[idx])
        op[1] += 1

    if op[2] > 0:
        op[2] -= 1
        dfs(idx + 1, now * nums[idx])
        op[2] += 1

    if op[3] > 0:
        op[3] -= 1
        dfs(idx + 1, int(now / nums[idx]))
        op[3] += 1

dfs(1, nums[0])

print(maxRes)
print(minRes)

백트래킹은 어렵다...