ndb-Part3- BFS,DFS-19 : 연산자 끼워넣기

알고리즘

ndb-Part3- BFS,DFS-19 : 연산자 끼워넣기

쭈돌s 2022. 3. 21. 20:21

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

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

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

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력 1 복사

2
5 6
0 0 1 0

예제 출력 1 복사

30
30

예제 입력 2 복사

3
3 4 5
1 0 1 0

예제 출력 2 복사

35
17

예제 입력 3 복사

6
1 2 3 4 5 6
2 1 1 1

예제 출력 3 복사

54
-24

힌트

세 번째 예제의 경우에 다음과 같은 식이 최댓값/최솟값이 나온다.

최댓값: 1-2÷3+4+5×6
최솟값: 1+2+3÷4-5×6

Step 1.[주어진 조건]

N개의 수, N-1개의 연산자가 주어진다.
주어진 수에 연산자를 사이에 집어 넣는다.
식의 계산은 연산자 우선순위를 무시하고 앞에서부터 순서대로 진행한다.
나눈셈은 몫의 정수만 취한다.
모든 식의 결과중 결과가 최대인 것과 최소인 것을 구한다.

풀이

Step 1.[주어진 조건]

N개의 수, N-1개의 연산자가 주어진다.
주어진 수에 연산자를 사이에 집어 넣는다.
식의 계산은 연산자 우선순위를 무시하고 앞에서부터 순서대로 진행한다.
나눈셈은 몫의 정수만 취한다.
- (음수 / 양수) 일경우 양수로 바꾼뒤 몫을 취한뒤
- 음수로 다시 변경한다.

모든 식의 결과중 결과가 최대인 것과 최소인 것을 구한다.

Step 2. [입력 조건]

n : 2<=N<=11 주어질 수의 개수
A1~An : 주어질 수
+, -, x, / 의 개수가 각 인덱스별로 주어짐

Step 3.[출력조건]

최대 값 출력(int)
최소 값 출력(int)

* 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다. -> int 변수만 써도 된다 (-21억 ~ 21억)

Step 4.[풀이]

결과값으로 사용할 최대값, 최소값을 세팅
연산자 콤비네이션 리스트 만들기
주어진 수의 리스트 만들기
연산자 콤비네이션만큼 연산하기
1. 각각의 연산을 위해 연산자 만큼 for문 돌리기
2. 주어진 수를 순서대로 연산하기
3. max, min으로 최소값, 최대값 출력하기

import math
import sys
from itertools import permutations
import operator

n = int(sys.stdin.readline().rstrip())
input_num = list(map(int, sys.stdin.readline().rstrip().split()))

# +, -, *, /
op = list(map(int, sys.stdin.readline().rstrip().split()))
operators = []
operator_idx = ['+', '-', '*', '/']
ops = {
    '+': operator.add,
    '-': operator.sub,
    '*': operator.mul,
    # itruediv : operator 기능 중 나누기 기능 (/),
    # https://docs.python.org/ko/3.7/library/operator.html
    '/': operator.itruediv,
}

# 결과 값 세팅
max_res = -float('inf') # - inf 안쓰고 처음에 0을 대입 했다가 틀렸었음.
min_res = float('inf')

for idx, count in enumerate(op):
    if count != 0:
        for _ in range(count):
            operators.append(operator_idx[idx])

operator_permutation_set = set(permutations(operators, n - 1))
for operator_set in operator_permutation_set:
    res_temp = input_num[0]
    for idx, operator in enumerate(operator_set):
        # math.trunc 소수점 버림
        res_temp = math.trunc(ops[operator](res_temp, input_num[idx + 1]))
    max_res = max(max_res, res_temp)
    min_res = min(min_res, res_temp)

print(max_res)
print(min_res)

DFS 로 풀기

전체 탐색을 해야 하므로 DFS, BFS 탐색을 생각 할 수 있다.

import sys

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

maximum = -1e9
minimum = 1e9

# dy = []


def dfs(depth, total, plus, minus, multiply, divide):
    
    global maximum, minimum
    # 마지막 연산자까지 계산을 끝냈다면
    if depth == N:
        maximum = max(total, maximum)
        minimum = min(total, minimum)
        return

    # temp_res = ''.join(map(str, [plus, minus, multiply, divide]))
    # if temp_res in dy:
    #     return

    """ 연산을 한 연산자에는 -1 을 더한다. """
    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multiply, divide)
        # mid_res = ''.join(map(str, [plus - 1, minus, multiply, divide]))
        # dy.append(mid_res)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multiply, divide)
        # mid_res = ''.join(map(str, [plus, minus - 1, multiply, divide]))
        # dy.append(mid_res)
    if multiply:
        dfs(depth + 1, total * num[depth], plus, minus, multiply - 1, divide)
        # mid_res = ''.join(map(str, [plus, minus, multiply - 1, divide]))
        # dy.append(mid_res)
    if divide:
        # int 로 변형하여 소수잠 아래자리는 버린다.
        dfs(depth + 1, int(total / num[depth]), plus, minus, multiply, divide - 1)
        # mid_res = ''.join(map(str, [plus, minus, multiply, divide - 1]))
        # dy.append(mid_res)


# 연산할 다음 숫자인덱스(깊이), (연산한)현재 숫자, +, -, *, /
dfs(1, num[0], op[0], op[1], op[2], op[3])
print(maximum)
print(minimum)

Step 4.[풀이]

결과로 사용할 max, min 변수를 만든다. (최소값, 최대값으로 초기화)

깊이 우선 탐색으로 전체 탐색을 한다.
1. dfs 함수를만든다.
2. 파라미터로 child에 전달 할 변수를 정한다.
  - 깊이(결과도출용), 합계(결과도출용), 연산자의 수(+,-,*,/)
3. dfs 의 재귀 조건을 만든다. (반드시 종료 될 수 있는 조건)
  - 최종 깊이에 도달 하였을 경우
  - max, min 을 비교하여 저장.
  - 종료
4. 다음 깊이로 가기전에 각각의 연산들을 진행한다.
  1. 각각의 연산자를 가지고 있는경우
  2. 합계와 다음 숫자를 해당 연산자로 연산.
  3. 연산된 수를 합계로 바꾼다.
  4. 인덱스를 올린다.
  5. 연산자를 1번 썼기 때문에 사용한 연산자의 수를 -1 카운트한다.
  6. 위의 조건으로 다시 DFS 함수를 실행한다.
시작 조건을 담은 DFS 함수를 실행. 합계에 연산할 첫번째 수를 넣는다.