[DFS/BFS/완전탐색]14888번 - 연산자 끼워넣기(DFS/완전탐색)

[백준] 14888번 - 연산자 끼워넣기

풀이 시간: 60분 이내

문제의 아이디어를 떠올리고 구현하는 것 자체는 30분 정도 걸렸는데 반례를 찾아 오류를 고치느라 시간이 오래 걸렸다. 추후 복습이 필요한 문제!

N개의 수와 N - 1 개의 연산자가 주어졌을 때, 만들 수 있는 식의 최댓값과 최솟값을 구하는 문제로 DFS로 풀거나 permutations 라이브러리를 이용하면 푸는 방법 2가지가 있다.

 

처음에 입력받은 +, -, *, / 의 개수(cnt)로부터 연산자 리스트(operator)를 만드는 것이 중요하다.

+, -, *, / 는 차례로 0, 1, 2, 3 이라고 생각하고 해당 개수에 따라 값을 넣어 리스트를 만든다.

+	-	*	/
0	1	2	3

예를 들어, 입력받은 연산자 개수가 0 1 0 2 이라면 operator는 [1, 3, 3]이 된다.

 

(풀이1) permutations 이용

1) 문제 해결 아이디어

순열을 구하기 위해 permutations를 이용했다. 

 

첫번째 오류. 시간초과

pypy3로 돌리니 해결되었다.

 

두번째 오류. 틀렸습니다

1% 후 바로 틀렸습니다가 나왔다. 나와있는 반례를 보고 틀린점을 찾아냈다.

음수 / 양수를 계산하는 부분의 식을 잘못 설정해서 난 오류였다.

 

<반례>

3

1 2 1

0 1 0 1

 

정답

-1

-1

2) 소스코드

from itertools import permutations
import sys
input = sys.stdin.readline

min_res = 1e9
max_res = -1e9
n = int(input())
num = list(map(int, input().split()))  # n개 정수
# 덧셈, 뺄셈, 곱셈, 나눗셈 개수
cnt = list(map(int, input().split()))
operator = []

for i in range(4):
  for j in range(cnt[i]):
    operator.append(i)

for o in permutations(operator):
  res = num[0]  # 첫번째 값으로 초기화
  for j in range(n - 1):
    # 덧셈이면
    if o[j] == 0:  res += num[j + 1]
    elif o[j] == 1:  res -= num[j + 1]
    elif o[j] == 2: res *= num[j + 1]
    elif o[j] == 3:
      # 둘 다 양수이면 몫을 계산
      res = int(res / num[j + 1])
      '''
      if(res > 0 and num[j + 1] > 0):  res //= num[j + 1]
      elif(res < 0):  res = -(-res // num[j + 1])
      '''
  if res > max_res:  max_res = res
  if res < min_res:  min_res = res
print(max_res, min_res, sep="\n")

풀이 시간: 40분 이내

(풀이2) DFS 이용

1) 문제 해결 아이디어

 

2) 소스코드

import sys
input = sys.stdin.readline

# DFS
def dfs(depth, res):
  global min_res, max_res
  if depth == n - 1:
    max_res = max(max_res, res)
    min_res = min(min_res, res)
    return

  for i in range(len(operator)):
    # 선택하지 않은 연산자라면
    if not check[i]:
      # 덧셈
      if operator[i] == 0:
        check[i] = True     
        dfs(depth + 1, res + num[depth + 1])
        check[i] = False
      # 뺄셈
      elif operator[i] == 1:
        check[i] = True   
        dfs(depth + 1, res - num[depth + 1])
        check[i] = False
      # 곱셈
      elif operator[i] == 2:  
        check[i] = True   
        dfs(depth + 1, res * num[depth + 1]) 
        check[i] = False
      # 나눗셈
      elif operator[i] == 3:
        check[i] = True   
        dfs(depth + 1, int(res / num[depth + 1]))
        check[i] = False
      
min_res = 1e9  
max_res = -1e9
n = int(input())
num = list(map(int, input().split()))  # n개 정수
# 덧셈, 뺄셈, 곱셈, 나눗셈 개수
cnt = list(map(int, input().split()))
operator = []
check = [False] * (n - 1)  # 선택 여부

for i in range(4):
  for j in range(cnt[i]):
    operator.append(i)

dfs(0, num[0])    
print(max_res, min_res, sep="\n")