[삼성SW기출문제] 14888번 연산자 끼워넣기

1. 문제 링크

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

14888번: 연산자 끼워넣기

 

2. 코드

이 문제는 총 2가지 풀이 방법이 있다.

 

1. 순열 구한 후, 완전 탐색으로 풀기

-> 이중 for문으로 시간복잡도 log(N^2)

-> 백준 Python3로는 시간초과 발생. PyPy3는 통과.

- 문제 소요 시간: 30분

from itertools import permutations

N = int(input())
A = list(map(int, input().split()))
o = list(map(int, input().split()))
operator = ['+', '-', '*', '/']
op = []
for i in range(len(o)):
    op += [operator[i]] * o[i]

max_ans, min_ans = -1e9, 1e9
orders = list(permutations(op, N - 1))

for order in orders:
    answer = A[0]
    for i in range(len(order)):
        if order[i] == '+':
            answer += A[i + 1]
        elif order[i] == '-':
            answer -= A[i + 1]
        elif order[i] == '/':
            if answer < 0:
                answer = -(abs(answer) // A[i + 1])
            else:
                answer //= A[i + 1]
        elif order[i] == '*':
            answer *= A[i + 1]

    max_ans = max(max_ans, answer)
    min_ans = min(min_ans, answer)

print(max_ans)
print(min_ans)

 

2. DFS 알고리즘으로 풀기 (재귀 이용)

- 문제 소요 시간: 29분

 

from itertools import permutations

N = int(input())
A = list(map(int, input().split()))
op = list(map(int, input().split())) # +, -, *, //

max_ans, min_ans = -1e9, 1e9

def dfs(i, answer, add, sub, mul, div):
    global max_ans, min_ans
    if i == N:
        max_ans = max(answer, max_ans)
        min_ans = min(answer, min_ans)
        return

    if add:
        dfs(i + 1, answer + A[i], add - 1, sub, mul, div)
    if sub:
        dfs(i + 1, answer - A[i], add, sub - 1, mul, div)
    if mul:
        dfs(i + 1, answer * A[i], add, sub, mul - 1, div)
    if div:
        dfs(i + 1, int(answer / A[i]), add, sub, mul, div - 1)


dfs(1, A[0], op[0], op[1], op[2], op[3])

print(max_ans)
print(min_ans)