[이코테] DFS/BFS - 연산자 끼워 넣기

🔔 문제

N개의 수로 이루어진 수열 A1, A2, ... AN이 주어집니다. 또, 수와 수 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어집니다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(x), 나눗셈(%)으로만 이루어져 있습니다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있는데 이때 주어진 수의 순서를 바꾸면 안됩니다. 예를 들어, 6개의 수로 이루어진 수열이 1,2,3,4,5,6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(x) 1개, 나눗셈(%) 1개인 경우에는 총 60가지의 식을 만들 수 있습니다. 예를 들어, 다음과 같은 식을 만들 수 있습니다.

1 + 2 + 3 - 4 x 5 % 6
1 % 2 + 3 + 4 - 5 x 6
1 + 2 % 3 x 4 - 5 + 6
1 % 2 x 3 - 4 + 5 + 6

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

1 + 2 + 3 - 4 x 5 % 6 = 1
1 % 2 + 3 + 4 - 5 x 6 = 12
1 + 2 % 3 x 4 - 5 + 6 = 5
1 % 2 x 3 - 4 + 5 + 6 = 7

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

입력

• 첫째 줄에 수의 개수 N(2<=N<=11)이 주어집니다.
• 둘째 줄에는 A1, A2, ... AN이 주어집니다. (1<=Ai<=100)
• 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(x)의 개수, 나눗셈(%)의 개수입니다.

출력

• 첫째 줄에는 만들 수 있는 식의 결과의 최댓값을 출력합니다.
• 둘째 줄에는 최솟값을 출력합니다.
• 최댓값과 최솟값이 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어집니다. 또한 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같습니다.

🎯 풀이방법

이 문제는 최대 11개의 수가 주어졌을 때, 각 수와 수 사이에
사칙연산 중 하나를 삽입하는 모든 경우에 대하여 만들어질 수 있는 결과의 최댓값 및 최솟값을 구하면 된다. 따라서 모든 경우의 수를 계산하기 위하여(완전 탐색) DFS 혹은 BFS를 이용하여 문제를 해결할 수 있다. 이 문제에서는 각 사칙연산을 중복하여 사용할 수 있기 때문에, 이 문제를 풀기 위해서는 중복 순열을 계산해야 한다. 예를 들어 n=4라고 하면, 사칙연산 중에서 중복을 허용하여 3개를 뽑아 나열하는 모든 경우를 고려해야 한다. 이는 파이썬의 중복 순열(product) 라이브러리를 이용하여 찾을 수도 있다. 다만, 본 문제에 대한 정답 소스코드는 itertools의 중복 순열(product) 클래스를 사용하지 않고 DFS를 이용하여 해결하였다.

💻 Python 코드

n = int(input())
# 연산을 수행하고자 하는 수 리스트
data = list(map(int, input().split()))
# 더하기, 빼기, 곱하기, 나누기 연산자 개수
add, sub, mul, div = map(int, input().split())

# 최솟값과 최댓값 초기화
min_value = 1e9
max_value = -1e9

# 깊이 우선 탐색(dfs) 메서드
def dfs(i, now):
    global min_value, max_value, add, sub, mul, div

    # 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
    if i == n:
        min_value = min(min_value, now)
        max_value = max(max_value, now)
    else:
        # 각 연산자에 대하여 재귀적으로 호출
        if add > 0:
            add -= 1
            dfs(i+1, now+data[i])
            add += 1
        if sub > 0:
            sub -= 1
            dfs(i+1, now-data[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i+1, now*data[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i+1, int(now/data[i]))
            div += 1

dfs(1, data[0])

print(max_value)
print(min_value)