[BOJ] 14888 - 연산자 끼워넣기

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

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

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

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

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

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

 

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

 

🚦 문제 유형

• 완전 탐색
• DFS/BFS, 순열

 

✏️ Solution

이 문제를 봤을 때 가장 쉽게 떠올릴 수 있는 방법은 연산자의 모든 경우의 수를 구하는 것 이다.

하지만 python의 순열 라이브러리 함수를 사용해 모든 경우의 수를 구한 뒤 연산을 진행하면 시간초과로 정답을 맞출 수 없다.

(PyPy3에서는 동작한다고 한다.)

완전 탐색 문제의 풀이 법에는 for문 사용, 순열/조합, BFS/DFS 등 여러가지가 있는데 이 문제를 재귀함수를 사용하는 DFS로 풀면 시간 초과 없이 정답을 맞출 수 있다.

따라서 이 문제의 모범 답안은 DFS를 사용한 풀이이다.

[풀이 방법]

1. 순열을 사용해 모든 경우의 수를 구하는 풀이
2. DFS를 사용해 모든 경우를 탐색하는 풀이

🎖 2번 풀이

사실 2번 풀이는 재귀함수 문제 풀 때 마다 이해가 직관적으로 되지 않아서 항상 힘겨웠다. 이런 문제는 누군가 풀이를 그림으로 설명해주면 너무 좋을 것 같은데 다른 사람들은 직관적 이해가 가능한 것인지 그림 설명을 못찾았다. 그래서 시간은 좀 걸리더라도 나만큼은 그림으로라도 이해해야 속이 시원할 것 같았다.

이해 순서: 코드 먼저 보기 👉 예시를 그려보며 이해하기 👉 코드 안보고 다시 작성해보기

코드는 다음과 같다.

from cmath import inf

N = int(input())
num = list(map(int,input().split(' ')))
add, sub, mul, div = map(int, input().split(' '))

max_value = -inf
min_value = inf

# DFS 탐색
def dfs(i, now):
    global min_value, max_value, add, sub, mul, div
    if i == N:
        max_value = max(max_value, now)
        min_value = min(min_value, now)
    else:
        if add > 0:
            add -= 1
            dfs(i+1, now+num[i])
            add += 1
        if sub > 0:
            sub -= 1
            dfs(i+1, now-num[i])
            sub += 1
        if mul > 0:
            mul -= 1
            dfs(i+1, now*num[i])
            mul += 1
        if div > 0:
            div -= 1
            dfs(i+1, int(now/num[i]))   # 음수를 양수로 나눌 때
            div += 1

dfs(1, num[0])

print(max_value)
print(min_value)

처음에 코드를 보고 dfs 함수에서 if문으로 연산자마다 dfs 함수를 재귀호출 하는게 어떻게 모든 경우의 수를 커버할 수 있는지 한번에 이해하기는 어려운 것 같다. 

먼저, 재귀함수의 종료조건인 i == N

• 현재 보고 있는 숫자가 마지막이면 연산이 끝났음을 의미함으로 최대, 최소 값을 구한다.

만약 아직 i가 N과 같지 않다면, 연산을 계속해야 한다.

 

예시를 보면서 dfs를 이해해보기로 했다. num = [3, 4, 5] 이고 연산자인 opr = [1, 0, 1, 0] 일 때 살펴보자.

1. 제일 처음 첫번째 원소인 3이 dfs 탐색의 시작이다. 👉 dfs(1, num[0])
숫자 3이 나온 후 나올 수 있는 연산자는 +, -, *, / 로 뻗어갈 수 있는데 코드에서는 덧셈 -> 뺄셈 -> 곱셈 -> 나눗셈 순서로 if 문이 돌기 때문에 제일 먼저 덧셈을 타고 내려간다.
숫자 뒤에 연산자가 펼쳐지는 동작이 있을 때 DFS를 호출한다고 생각하면 쉽다.

• 현재 덧셈이 1 이므로 3+4 = 7 을 하고 덧셈 연산자 개수를 감소한다. 그리고 다시 다음에 나올 연산자를 살펴봐야 하므로 DFS를 호출한다. 👉 dfs(2, now + num[1]) = dfs(2, 7)
• dfs(2, 7)에서도 덧셈 -> 뺄셈 -> 곱셈 -> 나눗셈 순으로 연산자 개수를 확인하고 개수가 0이면 계산하지 않고 넘어간다. (빨간 점선 엑스표는 전 dfs 호출에서 한번 썼기 때문에 0이 되어서 사용하지 못함)
• 이 상태에서 곱셈의 연산자 개수가 0보다 크므로 7 * 5 = 35을 하고 곱셈 연산자 개수를 감소한다. 그리고 다시 다음에 나올 연산자를 살펴봐야 하므로 DFS를 호출한다. 👉 dfs(3, now + num[2]) = dfs(3, 35)
• 이제 dfs(3, 35)를 실행하는 순간 i==N 의 조건에 걸려서(마지막 숫자라서) 최대, 최소값을 업데이트 한다.
  max_value = 35, min_value = 35

• dfs(3, 35)를 종료하고 곱셈의 개수를 다시 1 증가한다.
• 그리고 백트래킹으로 올라가면서 dfs(2, 7)도 종료하고 덧셈의 개수를 다시 1 증가한다.
• 다시 dfs(1, num[0])으로 돌아오고 아직 끝나지 않았으므로 다음 if문인 if sub < 0 을 조사한다.

 

2. dfs(1, num[0]) 일 때, sub > 0과 mul > 0 을 체크

여기서부터 1번과 동작이 비슷하다. 그림을 보면서 이해하면 더 쉽다.

• 뺄셈은 개수가 0이므로 계산하지 않고(=dfs 호출하지 않고) pass
• 곱셈은 개수가 1이므로 3 * 4 = 12이 되고 곱셈 연산자를 감소한다. 그리고 다시 다음에 나올 연산자를 살펴봐야 하므로 DFS를 호출한다. 👉 dfs(2, now + num[1]) = dfs(2, 12)
• dfs(2, 12)에서도 덧셈 -> 뺄셈 -> 곱셈 -> 나눗셈 순으로 연산자 개수를 확인하고 개수가 0이면 계산하지 않고 넘어간다.
• 이 상태에서 덧셈의 연산자 개수가 0보다 크므로 12 + 5 = 17을 하고 덧셈 연산자 개수를 감소한다. 그리고 다시 다음에 나올 연산자를 살펴봐야 하므로 DFS를 호출한다. 👉 dfs(3, now + num[2]) = dfs(3, 17)
• 이제 dfs(3, 17)를 실행하는 순간 i==N 의 조건에 걸려서(마지막 숫자라서) 최대, 최소값을 업데이트 한다.
  max_value = 35, min_value = 17
•  

 

3. mul > 0일 때 나머지 뺄셈, 곱셈, 나눗셈 체크  & 4. div < 0 조사

• dfs(3, 17)를 종료하고 덧셈의 개수를 다시 1 증가한다.
• 그리고 백트래킹으로 올라가면서 dfs(2, 12)도 종료하고 곱셈의 개수를 다시 1 증가한다.
• 다시 dfs(1, num[0])으로 돌아오고 아직 끝나지 않았으므로 다음 if문인 if div < 0 을 조사한다.
• 나눗셈의 개수는 0이므로 dfs를 호출하지 않고 현재 dfs는 종료된다.

 

5. dfs(1, num[0]) 최종 종료

• 마지막으로 dfs(1, num[0])이 종료되면서 최대, 최소값이 최종적으로 업데이트 된다.

이렇게 이해를 한 뒤 코드를 다시 짜보면 좀 더 쉽게 짜진다.

그림을 그리다 보면 모든 경우를 탐색하는 DFS 그래프 개념을 확인할 수 있다. 

 

🎖 1번 풀이

추가로 1번 풀이는 순열과 큐를 사용한 풀이이다.

모든 가능한 경우의 수를 큐에 넣어서 하나씩 pop 해보며 연산을 하는 방법이다.

from cmath import inf
import sys
from itertools import permutations
from collections import deque

N = int(input())
num = list(map(int, sys.stdin.readline().split(' ')))

opr = ['+', '-', '*', '//']
opr_input = list(map(int, sys.stdin.readline().split(' ')))
opr_list = []

# 사용가능한 연산자 리스트
for i in range(4):
    if opr_input[i] == 0:
        pass
    else:
        for j in range(opr_input[i]):
            opr_list.append(opr[i])

# 순열을 이용해 모든 경우의 수 생성
opr_case = list(permutations(opr_list, len(opr_list)))
q = deque(opr_case)

max_result = -inf
min_result = inf

while q:    # queue가 다 빌 때 까지
    now_cal = q.popleft()
    result = num[0]
    for i in range(1, len(num)):
        if now_cal[i-1] == '+':
            result += num[i]
        elif now_cal[i-1] == '-':
            result -= num[i]
        elif now_cal[i-1] == '*':
            result *= num[i]
        else:
            if result < 0:
                result = -(abs(result) // num[i])
            else:
                result = result // num[i]
            
    max_result = max(max_result, result)
    min_result = min(min_result, result)

print(max_result)
print(min_result)

 

⚙️ Review

dfs의 풀이를 다시한번 짚어보는 문제였다. 완전 탐색 문제는 완전 탐색이라는 것을 파악하기는 쉬운데 구현하기가 어려운 것 같다.

특히 재귀함수를 사용하는 문제는 여전히 어렵지만 이 문제를 통해 그려봄으로써 이해하려고 노력했으니 앞으로의 문제도 잘 풀고싶다.