[BOJ/백준] 14888. 연산자 끼워넣기 (Python)

🔎 문제

🔗 백준 14888번 연산자 끼워넣기

💡 풀이

반복, 순열

각 연산자가 몇개인지 입력받아 순열을 돌려 모든 경우의 수를 구한 다음, 모든 경우에 수에 대해 전부 다 계산하여 최대 최소를 구하는 방법이다.

파이썬 itertools의 permutation() 메소드를 이용해 쉽게 순열을 구할 수 있다.

op_num = '+' * tmp[0] + '-' * tmp[1] + '*' * tmp[2] + '/' * tmp[3]
op = [i for i in op_num]
op = permutations(op, N - 1) # 순열

이때, 각 연산자와 그것의 갯수를 곱해서 만든 문자열을 순열을 돌리면 중복된 경우의 수가 나온다. 이것을 제거하려면

op = list(set(op)) # 중복 제거

파이썬의 set을 이용하면 된다. 파이썬의 set은 순서가 없고, 중복된 값 없이 unique한 값을 가진다.
이렇게 중복을 제거하면 중복된 경우의 수를 또 계산하는 시간을 덜 수 있다.

이렇게 구한 리스트의 모든 원소로 주어진 숫자들에 대한 계산을 다 해보고, 최대최소를 구하면 된다.

DFS

반복 방식은 재귀 호출을 이용한 방법보다 시간이 많이 소요된다. 아마 이 문제는 DFS를 이용해 푸는 것이 의도일 것이다.

몇번째 계산인지 depth변수로 표시하고, depth가 숫자의 갯수와 같으면 return하여 탐색을 종료한다.

재귀 호출을 할 때는 다음과 같은 연산자 갯수 리스트를 넘겨주는데, 계산을 할 때마다 해당 연산자 수를 하나씩 감소시킨다.

덧셈	뺄셈	곱셈	나눗셈
4	1	0	2

만약 0개일 경우는 계산하지 않는다.

그리고 반복이든 DFS든 주의할 점은 나눗셈이다.

• 정수 나눗셈으로 몫만 취한다.
  • 이는 파이썬의 // 를 사용하면 된다.
• 음수를 양수로 나눌 때
  • 양수로 바꾼 뒤 계산하고, 다시 음수로 바꿔줘야 한다. 만약 이렇게하지 않으면 테스트케이스3의 답이 안나온다.

📃 소스코드

반복, 순열

from itertools import permutations
import sys

N = int(input())
nums = list(map(int, input().split()))
tmp = list(map(int, input().split()))

# +, -, *, /
op_num = '+' * tmp[0] + '-' * tmp[1] + '*' * tmp[2] + '/' * tmp[3]
op = [i for i in op_num]
op = permutations(op, N - 1) # 순열
op = list(set(op)) # 중복 제거

max = -sys.maxsize
min = sys.maxsize

for i in op:
    result = nums[0]
    for j in range(N - 1):
        if i[j] == '+':
            result += nums[j + 1]
        elif i[j] == '-':
            result -= nums[j + 1]            
        elif i[j] == '*':
            result *= nums[j + 1]
        else: # 나눗셈
            if result < 0:
                result *= -1
                result //= nums[j + 1]
                result *= -1
            else:
                result //= nums[j + 1]
    if result >= max:
        max = result
    if result < min:
        min = result

print(max)
print(min)

재귀

import sys

# +, -, *, /
def dfs(depth: int, nums: list, plus: int, minus: int, multiple: int, divide: int, result: int):
    global MAX, MIN
    
    if depth == len(nums) - 1:
        MAX = max(MAX, result)
        MIN = min(MIN, result)
        return
    
    if plus:
        dfs(depth + 1, nums, plus - 1, minus, multiple, divide, result + nums[depth + 1])
    if minus:
        dfs(depth + 1, nums, plus, minus - 1, multiple, divide, result - nums[depth + 1])
    if multiple:
        dfs(depth + 1, nums, plus, minus, multiple - 1, divide, result * nums[depth + 1])
    if divide:
        if result < 0:
            dfs(depth + 1, nums, plus, minus, multiple, divide - 1, (result*(-1) // nums[depth + 1]) * (-1))
        else:
            dfs(depth + 1, nums, plus, minus, multiple, divide - 1, result // nums[depth + 1])


N = int(input())
nums = list(map(int, input().split()))
op = list(map(int, input().split()))

MAX = -sys.maxsize
MIN = sys.maxsize

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

print(MAX)
print(MIN)

재귀(DFS)가 가장 빠르다.

카카오페이로 커피사기 ❤️ 토스,계좌로 커피사기 ❤️