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

 

 

---

풀이

# 연산자는 앞에서부터
# 나눗셈은 정수 나눗셈으로 몫만 취함
# 음수를 양수로 나눌 때, 양수로 바꾼뒤 몫을 구하고 음수로 변환
from itertools import permutations

N = int(input())
num = list(map(int, input().split()))
sign_list = list(map(int, input().split()))
sign = ['+', '-', '*', '/']

op = []

for i in range(len(sign_list)):
    for j in range(sign_list[i]):
        op.append(sign[i])


result = []
for i in permutations(op, N-1):
    calc = num[0]
    for j in range(1, N):
        if i[j-1] == '+':
            calc += num[j]
        elif i[j-1] == '*':
            calc *= num[j]
        elif i[j-1] == '/':
            calc = int(calc/num[j])
        elif i[j-1] == '-':
            calc -= num[j]

    result.append(calc)

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

순열을 이용해 연산자를 정렬해서 풀이하였다. 그런데, 순열은 시간복잡도가 O(n!)으로 너무 커서 Pypy3에서만 통과했다.

 

 

 

다른 풀이 이해

백트래킹을 이용한 풀이

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

max_result = - int(1e9)
min_result = int(1e9)

def dfs(add, sub, mul, div, sum, idx):
    global max_result, min_result
    if idx == n:
        max_result = max(max_result, sum)
        min_result = min(min_result, sum)
        return
        
    if add:
        dfs(add-1, sub, mul, div, sum + number[idx], idx + 1)
    if sub:
        dfs(add, sub-1, mul, div, sum - number[idx], idx + 1)
    if mul:
        dfs(add, sub, mul-1, div, sum * number[idx], idx + 1)
    if div:
        dfs(add, sub, mul, div-1, int(sum / number[idx]), idx + 1)
        
dfs(add, sub, mul, div, number[0], 1)
print(max_result)
print(min_result)

 

연산자 우선순위가 반영되지 않고 순서되고 연산되기 때문에 백트래킹을 사용할 수 있다.

 

---

백트래킹

왔던 길을 되돌아 가며 가지치기하는 방식으로 탐색하기 때문에 완전 탐색에 비해 수행 시간이 적게 걸린다.

ex) 미로찾기, n-Queen 문제, Map coloring, 부분집합의 합 문제 등에서 활용

 

• Promising : 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.
• Pruning : 해당 트리에서 조건에 맞지않는 노드는 더 이상 DFS로 깊이 탐색을 진행하지 않고 가지치기를 한다.

즉, 재귀를 이용한 완전 검색을 한 후, 가지치기를 추가하는 기법

 

 

1) 완전 검색

#부분집합 기본코드
def printSet(n):
    for i in range(n):
        if A[i] == 1:
            print(data[i], end = " ")
    print()
    
def powerset(k, n):            # k는 A배열의 k인덱스의 포함 유무를 판별한다.
    if n == k:
        printSet(k)
    else:
        A[k] = 1
        powerset(k+1, n)       # 배열 A에 체크하고 다음 인덱스로 넘어간다
        A[k] = 0               # 재귀로 되돌아와서 체크 했던걸 다시 원상복귀시킨다
        powerset(k+1, n)

data = 구하려는 리스트
n = len(data)                  # 부분집합을 구하는 리스트의 수
A = [0]* n                     # 포함 유무를 체크할 리스트 (0이 미포함, 1이 포함)

 

 

2) 가지치기

# 부분집합의 합
def powerset(k, n, sum):
    if sum > 10:          # 부분집합의 합을 구하는 문제에서 구하고자하는 값인 10을 넘는다면 더이상 계산할 필요가 없으므로 return해버린다.(가지치기)
        return
    if n == k:
        printSet(k, sum)
    else:
        A[k] = 1
        powerset(k+1, n, sum+data[k])       
        A[k] = 0               
        powerset(k+1, n, sum)

 

 

 

 

 

[python] 백트래킹(backtracking)

 

 

예제) n과 m(1)

[Python] 백트래킹 (+ DFS와 차이)

 

[백준BOJ] 단계별로 문제풀기 - 백트래킹 정답 및 후기(파이썬, python)

 

 

 

 

 

 

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

14888번: 연산자 끼워넣기