14888번 - 연산자 끼워넣기

문제

 

14888번: 연산자 끼워넣기 (acmicpc.net)

14888번: 연산자 끼워넣기

풀이 1

연산자는 순열로 나타낼 수 있지만, 연습을 위해 풀이는 DFS로 해보기로 했다.

순열 대신 DFS로 푼다는것, 즉 제한된 횟수만큼 경우의 가짓수를 찾아가는 것은 이미 연구소 문제에서 다뤄봤다. 연구소 문제에서는 벽을 3개 세우는 것을 조건으로 뒀으며, 그 조건을 만족했을 때 재귀를 탈출해서 바이러스 감염을 연산했었다. 이번에는 정확히 같은 방법으로, 연산자들을 모두 배열 했을 때 이 문제가 원하는 최대값, 최소값을 갱신해주는 작업을 해주면 된다.

# index는 입력받은 수들의 리스트 인덱스 이다.
def dfs_operators(index):
  global maxResult, minResult
  # 만약 마지막 숫자까지 연산을 완료 했으면 결과를 갱신한다.
  if index == n:
    maxResult = max(maxResult,answer)
    minResult = min(minResult,answer)
    return
  # 연산자 개수가 들어있는 리스트를 순회한다. + -> - -> * -> // 순.
  for i in range(4):
    # 만약 해당 연산자를 모두 소진했으면 넘어간다.
    if operList[i] == 0:
      continue
    # 연산자를 하나 소모하고, 다음 연산을 시행한다.
    operList[i] -= 1
    dfs_operators(index+1, operatorDict[i](now,numList[index]))
    # 모든 경우를 탐색할 수 있도록 이전 단계로 되돌아가는 작업이다.
    operList[i] += 1

코드

내 풀이

import sys

input = sys.stdin.readline
n = int(input().rstrip())
numList = list(map(int,input().split()))
operList = list(map(int,input().split()))

operatorNum = sum(operList)
maxResult = -int(1e9)
minResult = int(1e9)

operatorDict = {
  0:lambda a,b : a+b,
  1:lambda a,b : a-b,
  2:lambda a,b : a*b,
  3:lambda a,b : a//b if a>0 and b>0 else -(abs(a)//abs(b)),
}

def dfs_operators(index,now):
  global maxResult, minResult
  if index == n:
    maxResult = max(maxResult,now)
    minResult = min(minResult,now)
    return
  for i in range(4):
    if operList[i] == 0:
      continue
    operList[i] -= 1
    dfs_operators(index+1, operatorDict[i](now,numList[index]))
    operList[i] += 1

dfs_operators(1,numList[0])

print(maxResult)
print(minResult)

해답

n = int(input())
data = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

min_value = 1e9
max_value = -1e9

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)

 난 for 문을 돌며 만들어둔 연산식 딕셔너리를 이용한 반면, 해답은 각 if문 마다 연산식을 넣어주고 있다. 또한 나눗셈 부분에서 int(now/data[i]) 와 같이 작성하며 나눗셈 몫을 구하는데 c++와 같은 답을 구할 수 있도록 해놓은게 눈에 띈다.

풀이 2

간단한 dfs 문제이다. 연산자 개수는 N-1개로 항상 고정되어 있기 때문에, 숫자 인덱스가 N에 도달하면 answer를 갱신해주면 된다.

N = int(input())
A = list(map(int,input().split()))
# + - * /
oper = list(map(int,input().split()))


def dfs(idx,result):
    global max_value,min_value
    if idx == N:
        max_value = max(max_value, result)
        min_value = min(min_value, result)
        return
    # 덧셈
    if oper[0] > 0:
        oper[0] -= 1
        dfs(idx+1,result+A[idx])
        oper[0] += 1
    # 뺄셈
    if oper[1] > 0:
        oper[1] -= 1
        dfs(idx+1,result-A[idx])
        oper[1] += 1
    # 곱셈
    if oper[2] > 0:
        oper[2] -= 1
        dfs(idx+1,result*A[idx])
        oper[2] += 1
    # 나눗셈
    if oper[3] > 0:
        oper[3] -= 1
        if result < 0:
            dfs(idx+1,(abs(result)//A[idx]) * (-1))
        else:
            dfs(idx + 1, result // A[idx])
        oper[3] += 1


max_value = -int(1e9)
min_value = int(1e9)
dfs(1,A[0])
print(max_value)
print(min_value)