[Algorithm] 백준 14888 연산자 끼워 넣기 (삼성전자 SW 역량테스트 기출문제) | 파이썬

※ 14888 연산자 끼워 넣기

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

14888번: 연산자 끼워넣기

 

첫번째 문제 풀이 (시간 초과)

문제를 보고 먼저 생각해낸 해결방법은

1. 모든 조합 가능한 연산자 조합을 func_possible 리스트에 담는다. ex) func_possible=[['+', '*'], ['*', '+']]

2. 연산자 조합을 하나씩 꺼내서 숫자 배열과 계산한 후 answer_possible 리스트에 담는다. ex) answer_possible=[35,17]

3. 최댓값과 최솟값을 출력한다.

#입력
n = int(input())
func = []
num=list((map(int,input().split())))

plus, minus, mul, div = map(int,input().split())
for _ in range(plus):
    func.append('+')
for _ in range(minus):
    func.append('-')
for _ in range(mul):
    func.append('*')
for _ in range(div):
    func.append('/')

def do():
    #조합하기
    array = func
    k = len(func)
    used = [False for i in range(len(array))]
    func_possible=[]

    def backtrack_perm(arr):
        if len(arr)==k:
            #print(arr, end=" ")
            func_possible.append(arr)
            return

        for i in range(len(array)):
            if used[i]==False:
                used[i] = True
                backtrack_perm(arr+[array[i]])
                used[i] = False

    backtrack_perm([])

    #func_possible=[['+', '*'], ['*', '+']]

    #계산하기
    answer_possible=[]
    for i in range(len(func_possible)):
        result = []
        func_choose = func_possible[i]
        for j in range(len(func_choose)):
            result.append(num[j])
            result.append(func_choose[j])
        result.append(num[len(num)-1])

        answer = result[0]
        for i in range(len(result)):
            if result[i]=='+':
                answer = answer+result[i+1]
            if result[i]=='-':
                answer = answer-result[i+1]
            if result[i]=='*':
                answer = answer*result[i+1]
            if result[i]=='/':
                answer = int(answer/result[i+1])
        answer_possible.append(answer)

    return answer_possible

answer_possible=do()
print(max(answer_possible))
print(min(answer_possible))

프로그램 상에서 돌렸을 때는 정답이 출력되었지만 백준에 제출한 결과...시간초과...

 

두번째 문제 풀이 (백트래킹)

연산자 개수를 추적하며 최댓값과 최솟값을 갱신하는 방법으로 풀어보자.

n = int(input())
num=list((map(int,input().split())))
plus, minus, mul, div = map(int,input().split())

min_value = 1e9
max_value = -1e9

def dfs(i,now):
    global min_value, max_value, plus, minus, mul, div
    if i==n:
        min_value = min(min_value, now)
        max_value = max(max_value, now)

    else:
        if plus>0:
            plus-=1
            dfs(i+1,now+num[i])
            plus+=1
        if minus>0:
            minus-=1
            dfs(i+1,now-num[i])
            minus+=1
        if mul>0:
            mul-=1
            dfs(i+1,now*num[i])
            mul+=1
        if div>0:
            div-=1
            dfs(i+1,int(now/num[i]))
            div+=1

dfs(1,num[0])
print(max_value)
print(min_value)

백트래킹을 더 공부하자..!