[백준] 14888번(python 파이썬)

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

 

연산자에 대한 백트래킹 문제이다.

 

사실 푸는법은 바로 떠올라서 금방 풀었지만 정답이 제대로 나오지 않았다..

 

몇시간 동안 디버깅을 한 결과

 

음수 // 양수 를 하면 정수로 변환되는데 이때 내림을 해서 변환하는거 같다..

 

-1//3 결과가 -1로 나왔음...

-2//3 결과도 -1로 나옴

 

풀이

연자를 확인하면서 재귀를 실행한다.

중복해서 연산자가 있을경우 해당 연산자에 대해서 한번만 실행해도된다. 처음에 중복해서 실행하니까 실행 시간이 오래 걸렸다...

 

처음 풀이

n = int(input())
number = list(map(int, input().split()))
operator = list(map(int, input().split()))
result_max = -1e9
result_min = 1e9

def BackTrack(index, start):
    global result_max, result_min
    if index == n - 1:
        result_max = max(start, result_max)
        result_min = min(start, result_min)
        return

    for i in range(4):
        if operator[i % 4] == 0:
            continue

        for _ in range(operator[i % 4]): #해당 연산자가 여러개있을 경우 중복실행인데 없어도된다 생각해보니...
            operator[i % 4] -= 1
            BackTrack(index + 1, Operator(start, number[index + 1], i % 4))
            operator[i % 4] += 1


def Operator(x, y, oper):
    if oper == 0:
        return x + y
    elif oper == 1:
        return x - y
    elif oper == 2:
        return x * y
    else:
        if x < 0:
            result = (-x) // y
            return -result
        else:
            return x // y

BackTrack(0, number[0])
print(result_max)
print(result_min)

 

 

최적화

n = int(input())
number = list(map(int, input().split()))
operator = list(map(int, input().split()))
result_max = -1e9
result_min = 1e9

def BackTrack(index, start):
    global result_max, result_min
    if index == n - 1:
        result_max = max(start, result_max)
        result_min = min(start, result_min)
        return

    for i in range(4):
        if operator[i % 4] == 0:
            continue
        operator[i % 4] -= 1
        BackTrack(index + 1, Operator(start, number[index + 1], i % 4))
        operator[i % 4] += 1


def Operator(x, y, oper):
    if oper == 0:
        return x + y
    elif oper == 1:
        return x - y
    elif oper == 2:
        return x * y
    else:
        if x < 0:
            result = (-x) // y
            return -result
        else:
            return x // y

BackTrack(0, number[0])
print(result_max)
print(result_min)