연산자 끼워넣기 - BOJ 14888 삼성전자 SW 역량테스트

17 Feb 2021 in ALGORITHM

‘풀이시간 30분 , 시간제한 2초, 메모리제한 512MB, BOJ 14888 삼성전자 SW 역량테스트 (취코테 349p)’

연산자 끼워넣기 - BOJ 14888
이 문제에서 어떤식으로 접근할지를 상당히 애를 먹었다. 아직 구현적인 면에서 많은 공부가 필요하다고 생각된다;;

우선 연산을 할 수 리스트들을 입력 받고, 사칙연산의 수를 입력받아 각 사칙연산 변수에 저장한다.
그리고 최댓값과 최솟값을 초기화 해야하는데 최댓값은 가장 작은 -10억(-1e9), 최솟값은 가장 큰 10억(1e9)로 둔다. 이렇게 해야 최댓값이 점점 큰 값으로 갱신이 가능하고, 최솟값이 점점 작은값으로 갱신이 가능해진다.
그리고 DFS를 이용해 가능한 연산 순서의 경우를 모두 탐색한다.

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)