14888

날짜 : 2022. 12. 12

사용 언어 : python

 

문제

 

 

코드

import sys
from itertools import permutations

n = int(sys.stdin.readline())  # 수의 개수
num = list(map(int, sys.stdin.readline().split()))  # 숫자 입력
temp = list(map(int, sys.stdin.readline().split()))  # 덧셈, 뺄셈, 곱셈, 나눗셈
op = list()
for _ in range(temp[0]): op.append("+")
for _ in range(temp[1]): op.append("-")
for _ in range(temp[2]): op.append("*")
for _ in range(temp[3]): op.append("/")
max_value = -1e9
min_value = 1e9


def fun():
    global max_value, min_value
    for i in permutations(op, n-1):  # 연산자들에 대한 모든 순열
        t = num[0]
        for j in range(1, n):
            if i[j-1] == "+": t += num[j]
            elif i[j-1] == "-": t -= num[j]
            elif i[j-1] == "*": t *= num[j]
            elif i[j-1] == "/": t = int(t / num[j])
        max_value = max(max_value, t)
        min_value = min(min_value, t)
fun()
print(max_value)
print(min_value)

 

백트래킹 활용 풀이(출처 아래 기입)

# 백트래킹 (Python3 통과, PyPy3도 통과)
import sys

input = sys.stdin.readline
N = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))  # +, -, *, //

maximum = -1e9
minimum = 1e9


def dfs(depth, total, plus, minus, multiply, divide):
    global maximum, minimum
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)


dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)

 

풀이

순열풀이

- 각 연산에 대해서 +, -, *, / 를 개수에 따라 리스트에 저장한 후 permutation을 이용해 순열을 생성한다.

- 해당 순열에 따라서 연산자를 비교하고 그에따라 계산하면서 값을 생신한 후 아웃풋을 출력한다.

 

 

알게된 점

- 백트래킹 문제지만 다른 방식으로 풀 수 있었다.

 

 

참고 사이트

- DFS(모범답안) 참고: https://velog.io/@kimdukbae/BOJ-14888-연산자-끼워넣기-Python

[BOJ 14888] 연산자 끼워넣기 (Python)