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

문제

14888번

N개의 수로 이루어진 수열 A1, A2, A3 ... AN이 주어진다.

그리고 수 사이에 끼워줄 N-1개의 연산자가 주어진다. 연산자는 오직 +, -, x, / 만 있다.

이 때 주어진 수의 순서를 바꾸면 안 된다.

식의 연산은 우선순위를 무시, 무조건 앞에서부터 순서대로 진행한다. 나눗셈은 정수 나눗셈으로 몫만을 취하며, 음수를 양수로 나눌때는 양수로 바꾸고 몫을 취하고, 그 몫을 음수로 바꾼다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

이 때, 식의 결과가 최대인 것과 최소인 값을 구하라.

어떻게 풀면 좋을까?

주어진 수를 바꾸지 말라고 했다. 수는 건들지 말고, 그럼 연산자의 가능한 조합을 모두 구해야 하지 않을까? permutaion을 사용해 볼까?

풀이

우선 나는 DFS로 풀지 않았다. 결론적으로는 통과했는데, 다른사람들의 풀이를 보니 DFS가 많았고 시간효율도 좋다고 하더라.
실제로 DFS풀이가 시간이 많이 단축 된 것을 백준 시간에서 확인 할 수 있었다.

위가 DFS, 아래가 내 풀이.

내 풀이는 permutation을 활용했다.

from itertools import permutations

n = int(input())
numbers = list(map(int, input().split()))
plus, sub, mul, div = map(int, input().split())
operator = ['+'] * plus
operator += ['-'] * sub
operator += ['x'] * mul
operator += ['/'] * div
# 중복을 제거한 연산자 집합이다.
operator = list(set(permutations(operator, len(operator))))

result = []
# oper == ('-', '+', '+', '/', 'x') 와 같은 형태로 나온다.
for oper in operator:
		# 첫번째 값을 꺼내놓고, 인덱스 1 부터 계산해준다.
    number = numbers[0]
    for i in range(1, len(numbers)):
        if oper[i-1] == '+':
            number += numbers[i]
        elif oper[i-1] == '-':
            number -= numbers[i]
        elif oper[i-1] == 'x':
            number *= numbers[i]
        else:
            if number < 0 < numbers[i]:
                number = -(-number // numbers[i])
            else:
                number = number // numbers[i]
    result.append(number)

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

DFS 풀이다.

import math

n = int(input())
numbers = list(map(int, input().split()))
plus, sub, mul, div = map(int, input().split())

max_num = -math.inf
min_num = math.inf

def solution(num, idx, plus, sub, mul, div):
    global max_num, min_num
    if idx == n:
        max_num = max(max_num, num)
        min_num = min(min_num, num)
        return
    if plus:
        solution(num + numbers[idx], idx + 1, plus-1, sub, mul, div)
    if sub:
        solution(num - numbers[idx], idx + 1, plus, sub-1, mul, div)
    if mul:
        solution(num * numbers[idx], idx + 1, plus, sub, mul-1, div)
    if div:
        solution(int(num / numbers[idx]), idx + 1, plus, sub, mul, div-1)

def main():
    solution(numbers[0], 1, plus, sub, mul, div)
    print(max_num)
    print(min_num)