연산자 끼워넣기 Python 정리 및 구현 (백준 14888, 삼성 SW 역량테스트)

연산자 끼워넣기

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

Edge case

1. 문제조건

• dfs 사용가능한건 그냥 쓰는걸로

  • 다만 사용할때, 변수값이 공유되니, 만약 빼게되면 dfs 진행하고 더하기 다시 해줘서 보정해줘야해

---

Code

1. 1트

itertools 사용

• permutation 함수를 제작하여 사용했을 경우, 메모리 초과 발생

# 백준 14888
# https://www.acmicpc.net/problem/14888
# 삼성 기출
# 16:48 - 17:15

# 최댓값, 최솟값 찾기

# 결국 팩토리얼, 팩토리얼이네
from itertools import permutations


n = int(input())
numbers = list(map(int, input().split()))
nadd, nsub, nmul, ndiv = map(int, input().split())
ops = list()
for _ in range(nadd): ops.append('+')
for _ in range(nsub): ops.append('-')
for _ in range(nmul): ops.append('*')
for _ in range(ndiv): ops.append('/')

rmin = int(1e9)
rmax = -int(1e9)

def permutation(arr, n):
    if not arr:
        return [[]]

    result = []
    for i in range(len(arr)):
        elem = arr[i]
        rest_arr = arr[:i] + arr[i+1:]
        for p in permutation(rest_arr, n - 1):
            result.append([elem] + p)
    return result

def cal():
    result = numbers[0]
    for i in range(n-1):
        if po[i] == '+':
            result += numbers[i+1]
        elif po[i] == '-':
            result -= numbers[i+1]
        elif po[i] == '*':
            result *= numbers[i+1]
        elif po[i] == '/':
            if result < 0 and numbers[i+1] > 0:
                result = -1 * ((-1 * result) // numbers[i+1])
            else:
                result = result // numbers[i+1]
            
    return result

for po in permutations(ops, n-1):
    result = cal()
    rmin = min(result, rmin)
    rmax = max(result, rmax)

print(rmax)
print(rmin)

2. 2트

dfs 이용

# 백준 14888
# https://www.acmicpc.net/problem/14888
# 삼성 기출
# 14:50 - 15:15 # 25분

# 최댓값, 최솟값 찾기

from decimal import MIN_EMIN


n = int(input())
num = list(map(int, input().split()))
opn = list(map(int, input().split()))    # "+ - x /" 순서

min_answer = int(1e9)
max_answer = -int(1e9)

def dfs(a, s, m, d, answer, depth):
    global min_answer, max_answer
    if depth == n-1:
        min_answer = min(answer, min_answer)
        max_answer = max(answer, max_answer)
        return
    if a:
        dfs(a-1, s, m , d, answer+num[depth+1], depth + 1)
    if s:
        dfs(a, s-1, m, d, answer-num[depth+1], depth + 1)
    if m:
        dfs(a, s, m-1, d, answer*num[depth+1], depth + 1)
    if d:
        if answer < 0:
            tmp = -answer
            tmp = -1*(tmp // num[depth+1])
            dfs(a, s, m, d-1, tmp, depth + 1)
        else:
            dfs(a, s, m, d-1, answer//num[depth+1], depth+1)

if __name__ == "__main__":
    dfs(opn[0], opn[1], opn[2], opn[3], num[0], 0)
    print(max_answer)
    print(min_answer)