[Python/파이썬] 백준 알고리즘 14888 - 연산자 끼워넣기 (BackTracking)

 

 

 

<풀이>

"""
1. 아이디어
연산자들 숫자만큼 리스트로 연산자를 담고 백트래킹으로 순회한다.
그리고 각각의 결과값을 구해 비교하여 최댓값과 최솟값을 구한다.

2. 시간복잡도
- O(N^2) : 100 * 100 < 2억   -> 가능

3. 자료구조
N: int;
A: int[];
operator: str[];
canUsedCnt: int[];
maxValue, minValue: int;
"""
import sys
sys.setrecursionlimit(10 ** 4)

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
canUsedCnt = list(map(int, input().split()))

operatorList = []
maxValue = -10000000000
minValue = 10000000000


def backTracking():
    if len(operatorList) == N-1:
        result = A[0]
        for i in range(N-1):
            if operatorList[i] == 0:
                result += A[i+1]
            elif operatorList[i] == 1:
                result -= A[i+1]
            elif operatorList[i] == 2:
                result *= A[i+1]
            elif operatorList[i] == 3:
                result = int(result / A[i+1])
        global maxValue
        global minValue
        if result > maxValue:
            maxValue = result
        if result < minValue:
            minValue = result

    for i in range(4):
        if canUsedCnt[i] > 0:
            operatorList.append(i)
            canUsedCnt[i] -= 1
            backTracking()
            operatorList.pop()
            canUsedCnt[i] += 1


backTracking()
print(maxValue)
print(minValue)

다른 사람들 풀이를 보니 파라매터로 남은 연산자 개수를 표현했다.

하지만 위와 같이 리스트를 두고 for문으로 돌려 체크할 수도 있다.

백트래킹의 기본 골격이

def backTracking():
	if ~~:
            # ~~
            break
	for ~ in ~:
            if ~~:	# 가지치기(pruning)
                # ~~
                # ~~

이므로 위 풀이가 좀더 직관적이고 백트래킹스러운 풀이가 될 수 있다고 생각한다.

 

 

---

(추가) 22/3/18 더 간결한 풀이 ↓

import sys
sys.setrecursionlimit(10 ** 4)

input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
operator = list(map(int, input().split()))

maxResult = -1000000000
minResult = 1000000000


def backTracking(curResult, idx):
    if idx == N:
        global maxResult, minResult
        maxResult = max(maxResult, curResult)
        minResult = min(minResult, curResult)
        return
    li = [curResult+A[idx], curResult-A[idx], curResult*A[idx], int(curResult/A[idx])]
    for i, nextResult in enumerate(li):
        if operator[i]:
            operator[i] -= 1
            backTracking(nextResult, idx+1)
            operator[i] += 1


backTracking(A[0], 1)
print(maxResult)
print(minResult)

enumerate를 이용했다.

enumerate는 한번에 두개 인자밖에 못넣는다고 에러가 떠서.. li 배열을 따로 만들고 넣어줬다.

 

 

 

<핵심 정리>

1. 백트래킹 시 리스트를 만들고 append -> 재귀 -> pop 으로 구현한다.

2. 백트래킹의 핵심은 for문 밑에 if문으로 가지치기(pruning)