백준 14888) 연산자 끼워넣기 (python)

.

문제

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

초기 풀이

많이 생각할 것 없이, 백트래킹을 통해서 문제를 해결하면 된다 .

처음에는 아래와 같이 연산자들을 담는 giho라는 리스트를 활용해서 연산을 진행해주었다.

하지만 그러기 위해선 visited 리스트도 활용해야 하였고, visited에 있는지 확인해주느라 시간이 많이걸렸다.

n=int(input())
nums = list(map(int,input().split()))
lst = list(map(int,input().split()))
giho = []

for i in range(lst[0]):
    giho.append('+')

for i in range(lst[1]):
    giho.append('-')


for i in range(lst[2]):
    giho.append('*')


for i in range(lst[3]):
    giho.append('/')

visited = []

max_ans = -2e9
min_ans = 2e9
def back(temp,cnt):
    global max_ans
    global min_ans
    if cnt == n-1:
        max_ans = max(temp, max_ans)
        min_ans = min(temp, min_ans)
        return 
    for i in range(n-1):
        if i not in visited:
            visited.append(i)
            if giho[i]== '-':
                back(temp-nums[cnt+1],cnt+1)
            elif giho[i] == '+':
                back(temp+nums[cnt+1],cnt+1)
            elif giho[i] == '*':
                back(temp*nums[cnt+1],cnt+1)
            elif giho[i] == '/':
                back(int(temp/nums[cnt+1]),cnt+1)
            visited.pop()
back(nums[0],0)
print(max_ans)
print(min_ans)

개선된 풀이

기존에 기호들의 개수를 담는 lst라는 리스트를 이용하여 백트래킹을 진행해주었다.

기호를 하나 사용한다면 -1을 해준 후, backtracking 이후에 +1을 해주는 방식으로 구현하였다.

이를 통해 시간을 크게 단축시킬 수 있었다. 

n=int(input())
nums = list(map(int,input().split()))
lst = list(map(int,input().split()))

max_ans = -2e9
min_ans = 2e9
def back(temp,cnt):
    global max_ans
    global min_ans
    if cnt == n-1:
        max_ans = max(temp, max_ans)
        min_ans = min(temp, min_ans)
        return 
    for i in range(4):
        if lst[i]>0:
            lst[i]-=1
            if i == 0:
                back(temp+nums[cnt+1],cnt+1)
            elif i == 1:
                back(temp-nums[cnt+1],cnt+1)
            elif i == 2:
                back(temp*nums[cnt+1],cnt+1)
            elif i == 3:
                back(int(temp/nums[cnt+1]),cnt+1)
            lst[i]+=1
back(nums[0],0)
print(max_ans)
print(min_ans)