백준 14888 - 연산자 끼워넣기

 

처음 든 생각

- 연산자를 하나씩 다 끼워넣어서 확인해도 될까?

-> 피연산자가 최대 11개 이므로 연산자는 10개 사용 가능 즉, 10! 가지의 경우의 수가 최대이므로 완전 탐색해도 되겠다.

- 그 다음은 백트래킹해가면서 모든 연산을 재귀적으로 수행하면 되겠다

 

나의 답

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
operators_list = list(map(int,input().split()))

max_value = -10000000000
min_value = 10000000000

def search(idx, operators,result):
    if idx == N:
        global max_value,min_value
        max_value = max(max_value,result)
        min_value = min(min_value,result)
        return
    else:
        for i in range(4):
            if i == 0 and operators[i]>0:
                operators[i] -= 1
                result = result + arr[idx]
                search(idx+1, operators,result)
                result = result - arr[idx]
                operators[i] += 1
            elif i == 1 and operators[i]>0:
                operators[i] -= 1
                result = result - arr[idx]
                search(idx+1, operators,result)
                result = result + arr[idx]
                operators[i] += 1
            elif i == 2 and operators[i]>0:
                operators[i] -= 1
                result = result * arr[idx]
                search(idx+1, operators,result)
                result = result // arr[idx]
                operators[i] += 1
            elif i == 3 and operators[i]>0:
                operators[i] -= 1
                if result < 0:
                    result = -result
                    result = result // arr[idx]
                    result = -result
                else:
                    result = result // arr[idx]
                search(idx+1, operators,result)
                if result < 0:
                    result = -result
                    result = result * arr[idx]
                    result = -result
                else:
                    result = result * arr[idx]
                operators[i] += 1

search(1,operators_list,arr[0])
print(max_value)
print(min_value)



코드가 길어보이지만 연산자에 대한 계산을 개별적으로 수행해서 길어진 것이다.

 

먼저 함수는 몇번재 연산인지 체크할 인덱스, 계산 후 남은 연산자들, 그리고 결과값을 매개변수로 받는다.

백트래킹할 때마다 다시 돌아오거나 그 다음 연산을 수행하기 위해서 남은 연산자와 결과값이 필요하다. 

 

그 다음은 각각의 연산자에 대한 코드이다.

+ 연산자가 있으면 결과값에 대해서 + 연산을 수행하고 또 이어서 탐색한다.

이 때 + 연산자의 개수는 1개 감소시키고, 결과값도 + 연산을 수행한 결과값을 매개변수로 전달한다.

그렇게 재귀적으로 계속해서 수행해나간 후 마지막 피연산자에 대한 연산까지 수행하면 최댓값, 최솟값을 할당해주는 처리를 해주면 된다.

 

만약 마지막 연산까지 수행하면 백트래킹을 위해서 단계별 복원을 해줘야한다.

그 부분이 search 재귀함수 실행 이후에 필요한 부분이다.

 

---

백트래킹의 큰 맥락을 따지면 이렇다.

 

1. 시작점을 설정한 후 탐색을 시작한다.

2. 마지막에 도달했을 때의 상황(재귀 탈출 조건)에 대해서 설정해준다.

3. 계속해서 탐색을 해야하는 상황이면 재귀적으로 탐색을 진행하고

4. 한 단계의 탐색이 완료될 경우 다시 원상복구시키는 과정을 통해 백트래킹이 가능하도록 한다.

 

추가) 결과값은 그 때 그 때 계속 바뀌므로 매개변수로 전달하여 임시적으로 저장해서 써야될 것 같다.