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

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

14888번: 연산자 끼워넣기

아이디어

• 부호의 개수만큼 부호가 들어있는 배열 생성
• 그 배열의 수열의 경우의 수를 구하는 백트래킹 생성
• 경우가 만들어지면 계산하여 리스트에 저장
• 리스트에서 최대 최소값을 출력

구현 (시간초과)

import sys
input = sys.stdin.readline

# 부호가 올 수 있는 모든 경우의 수 백트래킹
def back():
    if '+' not in r and '-' not in r and '*' not in r and '//' not in r:
        result.append(cal(c))
        return
    for i in range(len(r)):
        if r[i] != 0:
            c.append(r[i])
            r[i] = 0
            back()
            r[i] = c.pop()

#계산 함수
def cal(c):
    res = z[0]
    for i in range(len(c)):
        if c[i] == "+":
            res += z[i+1]
        elif c[i] == "-":
            res -= z[i+1]
        elif c[i] == "*":
            res *= z[i+1]
        elif c[i] == "//":
            if abs(res) < z[i+1]:
                res = 0
            else:
                res //= z[i+1]
    return res

n = int(input())
z= list(map(int, input().split()))
t = list(map(int, input().split()))
y = ['+', '-', '*', '//']
r = []

# 부호의 개수만큼 배열에 넣기
for i in range(4):
    for j in range(t[i]):
        r.append(y[i])

result = []
c= []

back()

print(max(result))
print(min(result))

신간초과... ㅠ

틀린 원인 분석

• 부호의 개수만큼 부호가 들어있는 배열을 만드는 작업에서 시간초과가 나는 것 같다.
• 그냥 처음 받을 때 각 다른 변수로 받아 백트래킹을 진행하면?

구현(정답)

import sys
input = sys.stdin.readline

# 부호가 올 수 있는 모든 경우의 수 백트래킹
def back(i, arr):
    global add, sub, mul, div, maxv, minv
    if i == n:
        maxv = max(maxv, arr)
        minv = min(minv, arr)
    else:
        if add > 0:
            add -= 1
            back(i+1, arr + li[i])
            add += 1
        if sub > 0:
            sub -= 1
            back(i+1, arr - li[i])
            sub += 1
        if mul > 0:
            mul -= 1
            back(i+1, arr*li[i])
            mul += 1
        if div > 0:
            div -= 1
            back(i+1, int(arr/li[i]))
            div += 1

n = int(input())
li = list(map(int, input().split()))
add, sub, mul, div = list(map(int, input().split()))

maxv = int(-1e9)
minv = int(1e9)

back(1, li[0])

print(maxv)
print(minv)

나이스!

마무리

• 백트래킹에 대해서는 이해하고 있지만 문제를 봤을 때 구체적으로 어떻게 코드를 짤지 아직 미숙하다... 많이..
• 하나 더 풀어보자