[DFS/BFS] 이코테 (파이썬) 연산자 끼워 넣기 풀이

[문제]

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어집니다. 또, 수와 수 사이에 끼워 넣을 수 있는 N-1개의 연산자가 주어집니다.

 

연산자는 덧셈 (+), 뺄셈 (-), 곱셈 (*), 나눗셈 (/) 으로만 이루어져 있습니다.

 

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

 

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(*), 나눗셈(/) 

 

1개인 경우에는 총 60가지의 식을 만들 수 있습니다. 

 

.

.

.

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

 

[입력 조건]

1. 첫째 줄에 수의 개수 N(2 <= N <= 11)이 주어집니다.

 

2. 둘째 줄에는 A1, A2, ..., AN이 주어집니다. (1 <= Ai <= 100)

 

3. 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(*)의 개수, 나눗셈(/)의 개수입니다.

 

[출력 조건]

1. 첫째 줄에 만들 수 있는 식의 결과의 최댓값을 출력합니다.

 

2. 둘째 줄에는 최솟값을 출력합니다.

 

3. 최댓값과 최솟값이 항상 -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

 

 

[내 풀이]

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 메서드 호출
dfs(1, data[0])

# 최댓값과 최솟값 출력
print(max_value)
print(min_value)

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저