[알고리즘/백준] 15658번 : 연산자 끼워넣기(2)(python)

백트래킹을 이용해서 푸는 문제이다. 처음에는 연산자 부분에 for문을 넣어서 풀었는데 생각해보니 어짜피 +부터 처리할텐데 for문을 쓰지않고 if문을 + -> - -> * -> / 이 순으로 넣으면 된다...

나는 나누기에 두가지로 나눴는데 python은 int(음수 나누기)를 하면 된다.

def dfs(depth, total):
    global Max
    global Min
    if depth == N:
        if Max < total:
            Max = total

        if Min > total:
            Min = total
        return

    for i in range(4):
        if i == 0 and op[i]:
            op[i] -= 1
            dfs(depth + 1, total + a[depth])
            op[i] += 1
        elif i == 1 and op[i]:
            op[i] -= 1
            dfs(depth + 1, total - a[depth])
            op[i] += 1
        elif i == 2 and op[i]:
            op[i] -= 1
            dfs(depth + 1, total * a[depth])
            op[i] += 1
        elif i == 3 and op[i]:
            op[i] -= 1
            if total >= 0:
                dfs(depth + 1, total // a[depth])
            else:
                dfs(depth + 1, -(-total // a[depth]))
            op[i] += 1


N = int(input())
a = list(map(int, input().split()))
op = list(map(int, input().split()))
Max = -1e10
Min = 1e10
dfs(1, a[0])
print(Max)
print(Min)

바꾼 후 코드

def dfs(depth, total):
    global Max
    global Min
    if depth == N:
        if Max < total:
            Max = total

        if Min > total:
            Min = total
        return
    if op[0] > 0:
        op[0] -= 1
        dfs(depth + 1, total + a[depth])
        op[0] += 1

    if op[1] > 0:
        op[1] -= 1
        dfs(depth + 1, total - a[depth])
        op[1] += 1

    if op[2] > 0:
        op[2] -= 1
        dfs(depth + 1, total * a[depth])
        op[2] += 1

    if op[3] > 0:
        op[3] -= 1
        dfs(depth + 1, int(total / a[depth]))
        op[3] += 1
N = int(input())
a = list(map(int, input().split()))
op = list(map(int, input().split()))
Max = -1e10
Min = 1e10
dfs(1, a[0])
print(Max)
print(Min)