[백준] 연산자 끼워넣기 - 14888

14888번: 연산자 끼워넣기

---

백트래킹 문제이다.

첫 풀이에서는, 연산자들의 남은 사용 횟수를 dict로 만들어서 함수의 인자로 copy하여 넘겨주었다.

정답은 맞았지만 상위 등수의 소스코드와 비교해보니 실행시간이 약 2.5배정도 차이가 났다...

 

이 문제에서 배운 것들

• copy() 사용을 지양하자.
• *args를 이용한 함수로의 매개변수 전달법
• 코드를 수정할 때, 복붙한 후 제대로 수정했는지 확인하자. 대충 확인해서 틀리면 시간이 많이 잡아먹힌다.

---

파이썬3 소스코드 (첫 코드)

import copy


def recursive_search(idx, val, N, A, operators):

    global answers
    
    if idx == N-1:
        answers.append(val)
        return

    if all(x == 0 for x in operators.values()):
        return
    else:
        if operators["+"] > 0:
            op_copy = copy.copy(operators)
            op_copy["+"] -= 1
            recursive_search(idx+1, val+A[idx+1], N, copy.copy(A), op_copy)
        if operators["-"] > 0:
            op_copy = copy.copy(operators)
            op_copy["-"] -= 1
            recursive_search(idx+1, val-A[idx+1], N, copy.copy(A), op_copy)
        if operators["*"] > 0:
            op_copy = copy.copy(operators)
            op_copy["*"] -= 1
            recursive_search(idx+1, val*A[idx+1], N, copy.copy(A), op_copy)
        if operators["/"] > 0:
            op_copy = copy.copy(operators)
            op_copy["/"] -= 1
            if val < 0:  # 음수를 양수로 나누는 경우
                recursive_search(idx+1, -((-val)//A[idx+1]), N, copy.copy(A), op_copy)
            else:
                recursive_search(idx+1, val//A[idx+1], N, copy.copy(A), op_copy)


N = int(input())
A = list(map(int, input().split(" ")))
temp = list(map(int, input().split(" ")))
operators = {
    "+": temp[0],
    "-": temp[1],
    "*": temp[2],
    "/": temp[3]
}
answers = []
recursive_search(0, A[0], N, A, operators)

answers.sort()
print(answers[-1])
print(answers[0])

 

파이썬3 소스코드 (수정한 코드)

def backtrack(idx, val, A, plus, minus, multi, divide):

    global N, answers
    
    if idx == N:
        answers.append(val)
        return
    else:
        if plus:
            backtrack(idx+1, val+A[idx], A, plus-1, minus, multi, divide)
        if minus:
            backtrack(idx+1, val-A[idx], A, plus, minus-1, multi, divide)
        if multi:
            backtrack(idx+1, val*A[idx], A, plus, minus, multi-1, divide)
        if divide:
            if val < 0:  # 음수를 양수로 나누는 경우
                backtrack(idx+1, -((-val)//A[idx]), A, plus, minus, multi, divide-1)
            else:
                backtrack(idx+1, val//A[idx], A, plus, minus, multi, divide-1)


N = int(input())
A = list(map(int, input().split(" ")))
operators = list(map(int, input().split(" ")))
answers = []

backtrack(1, A[0], A, *operators)

answers.sort()
print(answers[-1])
print(answers[0])