[백준-Python] 문제 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억보다 작거나 같다.

---

풀이

def dfs(depth):
    global _max, _min

    # 재귀 탈출 조건 : depth가 연산자의 갯수와 동일할때.
    # max와 min값을 연산하여 대입 후 재귀를 탈출한다.
    if depth == (N-1):
        if visited[-1] > _max:
            _max = visited[-1]
        if visited[-1] < _min:
            _min = visited[-1]
        return

    for index in range(0, 4):  # 연산자의 종류가 4개로 정해져 있으므로, 반복횟수를 4회로 고정.
        if operators[index] > 0:  # 연산자가 있을때만 진행.
            operators[index] -= 1  # 사용한 연산자를 제거한다는 의미로, -1 연산을 수행한다.

            if index == 0:
                visited.append(visited[-1] + seq[depth + 1])
            elif index == 1:
                visited.append(visited[-1] - seq[depth + 1])
            elif index == 2:
                visited.append(visited[-1] * seq[depth + 1])
            elif index == 3:
                if visited[-1] < 0:  # 문제 조건을 충족시키기 위함. (음수를 양수로 나누는 경우)
                    visited.append(-(abs(visited[-1]) // seq[depth + 1]))
                else:
                    visited.append(visited[-1] // seq[depth + 1])
            dfs(depth+1)
            visited.pop()
            operators[index] += 1


N = int(input())
seq = list(map(int, input().split()))  # 수열 입력
operators = list(map(int, input().split()))  # 덧셈, 뺄셈, 곱셈, 나눗셈
visited = [seq[0]]  # 수열의 가장 첫번째 숫자를 대입.

_max = float('-inf')  # 최대값 비교를 위해, 최소값을 대입.
_min = float('inf')  # 마찬가지로 최대값을 대입.

dfs(0)  # 재귀 호출

print(_max)
print(_min)

---

정리

백트래킹 / 브루트포스 알고리즘을 DFS로 구현하였다.

재귀함수 안쪽에서 연산자를 하나씩 뽑아서 연산을 수행하며, 모든 경우의 수를 점검한다. 그리고 매 단계마다, visited 리스트에 누적 연산 값을 append() 로 붙여나간다. 그렇게 마지막까지 연산이 끝나면, 탈출 조건에서 visited 리스트의 마지막 index에 있는 값이 최종 연산 결과값이 된다.

예를 들어, 백준 홈페이지의 예제 입력 2번의 흐름은 다음과 같다.

1. 최초에 dfs(0) 함수가 호출되었을 때, 변수들의 상황은 다음과 같다.

index = 0  # 반복문의 index 값
depth = 0  # 재귀 단계

seq = [3, 4, 5]  # 입력받은 수열
visited = [3]
operators = [1, 0, 1, 0]  # 남은 연산자 : 덧셈 1, 곱셈 1

2. 재귀함수 내부에서 operators의 첫번째 연산자인 덧셈 하나를 뽑아오고, 수열에서 재귀의 depth+1 인덱스의 값과 연산한 값을 visited에 append()한다. 그리고 depth+1을 인수로 하여 재귀를 호출한다.

index = 0  # 반복문의 index 값
depth = 1  # 재귀 단계

seq = [3, 4, 5]
visited = [3, 7]  # (3 + 4) 연산값인 7을 append()
operators = [0, 0, 1, 0]  # 남은 연산자 : 곱셈 한개

3. 동일한 로직으로 한 번 더 반복하면, 다음과 같은 상태가 된다.

index = 2  # 반복문의 index 값
depth = 2  # 재귀 단계

seq = [3, 4, 5]
visited = [3, 7, 35]  # (7 * 5) 연산값인 35를 append()
operators = [0, 0, 0, 0]  # 남은 연산자 : 없음.

4. 남은 연산자가 없다면, 재귀의 탈출 조건으로 진입하여 min과 max값을 대입처리한 뒤 재귀를 탈출한다.
5. 재귀 내부의 반복문으로 인해서 index 값이 2가 되었을 때, 다시 연산을 진행한다. index의 값이 2이므로, 이번엔 곱셈 연산을 먼저 진행한다.

index = 2  # 반복문의 index값
depth = 0  # 재귀 단계

seq = [3, 4, 5]  
visited = [3]  # 재귀를 탈출할 때 마다, visited.pop() 연산을 수행한다.
operators = [1, 0, 1, 0]  # 남은 연산자 : 덧셈 한개, 곱셈 한개

...
...

index = 2  # 반복문의 index값
depth = 1  # 재귀 단계

seq = [3, 4, 5]  
visited = [3, 12]  # (3 * 4) 연산값인 12를 append()
operators = [1, 0, 0, 0]  # 남은 연산자 : 덧셈 한개

...
...

index = 0  # 반복문의 index값
depth = 2  # 재귀 단계

seq = [3, 4, 5]  
visited = [3, 12, 17]  # (12 + 5) 연산값인 17을 append()
operators = [0, 0, 0, 0]  # 남은 연산자 : 없음.

6. 최종적으로 결과값이 아래처럼 출력된다.

3  
3 4 5  
1 0 1 0  
최대값 : 3 + 4 \* 5 = 35  
최소값 : 3 \* 4 + 5 = 17