[백준] 14888번: 연산자 끼워넣기 - 파이썬/python

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

접근 방식

- 연산자를 끼워놓는 조합의 수와 이를 기술적으로 구현하는 방법

- or 백트래킹(dfs)

 

코드 풀이

n = int(input())
num = list(map(int, input().split()))
op = list(map(int, input().split()))

maxi = -1e9 # 초기 값, 재귀를 거치며 최대값이 계속 업데이트 됨
mini = 1e9 # 초기 값, 재귀를 거치며 최소값이 계속 업데이트 됨

def dfs(depth, total, plus, minus, multi, divide):
    global maxi, mini
    if depth == n: # 모든 사칙연산을 전부 배치했다면
        maxi = max(total, maxi) # 최대값
        mini = min(total, mini) # 최소값
        return
        
    # depth != n 인 경우 재귀 처리
    if plus:
        dfs(depth + 1, total + num[depth], plus - 1, minus, multi, divide)
    if minus:
        dfs(depth + 1, total - num[depth], plus, minus - 1, multi, divide)
    if multi:
        dfs(depth + 1, total * num[depth], plus, minus, multi - 1, divide)
    if divide:
        dfs(depth+1, int(total / num[depth]), plus, minus, multi, divide-1)
        # total//num[depth] 사용 시 음수의 나눗셈에서 문제 제시 조건대로 몫을 내지 않음

dfs(1, num[0], op[0], op[1], op[2], op[3]) # total 초기값은 nums[0]
print(maxi)
print(mini)

해당 문제는 제시된 고정된 숫자 사이에, 연산자를 조합하여 배치한 계산 결과의 최대값과 최소값을 출력하는 문제입니다. 연산자의 모든 조합의 경우를 테스트해보며 최대와 최소값을 조사해야 하기 때문에 브루트포스의 문제에 속합니다. 하지만 itertools 내의 combinations, permutations 등을 활용한다면 시간복잡도가 높아 Python에서는 시간초과가 발생합니다. 따라서 Python을 활용하여 문제를 풀고자 한다면 순열 조합을 활용하는 방법보다는 백트래킹(DFS)의 재귀를 활용하여 풀 수 있는 문제입니다.

먼저 숫자의 갯수를 n에 할당해 주고, 숫자 정보와 연산자의 갯수를 각각 num 리스트와 op 리스트에 저장해줍니다. 그리고 dfs 재귀 함수를 선언하는데, 재귀는 op 리스트에 할당된 4개의 원소가 모두 0이 되고, depth, 즉 재귀의 깊이가 n와 같아질 때까지 반복되게 됩니다. 위의 코드가 직관적으로 이해되지 않아 시간이 많이 소요되었는데 예시를 들어 설명해 보도록 하겠습니다. 예를 들어 n = 4, num = [1, 2, 3, 4], op = [1, 1, 1, 0] 을 input으로 받은 경우입니다. 직관적으로 4 개의 숫자 사이 3개의 공간에 서로 다른 3 개의 연산자를 배치해야 하므로 3! 즉 6개의 연산값을 구할 수 있으며 이의 최소값과 최대값을 출력하면 됩니다. 그럼 재귀는 어떻게 이루어질까요?

 

먼저 dfs(1, num[0], op[0], op[1], op[2], op[3]) 을 통해 dfs 함수가 시작됩니다.

depth != 4 이므로 if plus 내의 재귀로 들어가게 됩니다.(1) 이때 함수 내의 depth, total, plus, minus, multi, divide 인자들이 업데이트 됩니다. 여전히 depth !=4이므로 if minus 내의 재귀로 들어가게 됩니다.(2)  함수 내의 인자들이 다시 한 번 업데이트 되며, 여전히 depth !=4이므로 if multi 내의 재귀로 들어가게 됩니다.(3) 이 때 depth == 4가 만족되며 이 때의 total 값은 1 + 2 - 3 * 4 를 거친 값입니다. 이 total 값은 첫 번째 경우의 수에 해당하는 값입니다.

그리고 다시 재귀 함수의 바깥쪽부터 나오게 되는데, if multi에서 나오고 (3) if minus에서 나온 후 (2) 다시 if multi 내의 재귀로 들어갑니다.(2) 함수 내의 인자들이 업데이트 된 후 if minus 내의 재귀로 들어가게 됩니다. (3) 이 때 depth == 4가 만족되며 이 때의 total 값은 1 + 2 * 3 - 4를 거친 값입니다. 이 total 값은 두 번째 경우의 수에 해당하는 값입니다.

같은 방법으로 세 번째부터 여섯번째까지의 total 값을 구할 수 있습니다. 이는 max, min 함수를 통해 maxi, mini에 업데이트를 반복하게 되는데 global 처리를 통해 함수 바깥에서도 활용할 수 있으므로 total 값을 누적하여 비교할 수 있습니다. 

 

오답 이유

문제를 풀며 if divide에서 total을 업데이트 시킬 때 total // num[depth]를 활용하면 오답이 발생했습니다. 이는 음수의 나눗셈 처리 시, 몫을 문제에서 설명한  C++14의 기준에 맞게 설명하지 못하기 때문입니다. 예를 들어 -4 // 5 는 -1을 출력하며 int(-4//5)는 0을 출력합니다.

 

메모

if plus: 는 plus 변수가 True이면, 즉 0이 아니면 if 내의 절을 실행시킨다는 의미입니다.