백준 : 14888 연산자 끼워넣기

백준 : 14888 연산자 끼워넣기

문제 접근

• N개의 수가 주어지고, 그 사이에 넣을 수 있는 +, , , // 연산자의 개수가 주어집니다.
• 모든 연산자를 한 번씩 사용하여 식을 만들 수 있고,
• 가능한 모든 결과 중 최댓값과 최솟값을 출력해야 합니다.

각 숫자 사이에 들어갈 연산자의 조합을 모든 경우의 수로 시도해봐야 한다. 즉 완전 탐색이 필요하고, 이 때 DFS + 백트래킹이 가장 적합하다.

최종 코드

import sys, operator
input = sys.stdin.readline

def dfs(index, current):
    global maxV, minV
    # 모든 숫자를 다 사용했다면 최대/최소값 갱신
    if index == N :
        maxV = max(maxV, current)
        minV = min(minV, current)
        return 
    # 4가지 연산자(+, -, *, //)를 하나씩 시도
    for i in range(4):
        if ops[i] > 0 :     # 해당 연산자가 아직 남아있다면
            ops[i] -= 1     # 사용
            nextV = op_func[i](current, num[index]) # 현재 값과 다음 숫자를 연산
            dfs(index+1, nextV) # 다음 숫자 위치로 재귀 호출
            ops[i] += 1         # 연산자 되돌리기

N = int(input())
num = list(map(int, input().split()))
ops = list(map(int, input().split()))
# 연산자 함수 리스트 (마지막은 문제 조건에 맞춘 나눗셈)
op_func = [operator.add, operator.sub, operator.mul, lambda x, y: -(-x // y) if x < 0 else x // y]

# 결과 저장용 변수 (초기값은 무한/음의 무한)
maxV = -float('inf')
minV = float('inf')

# DFS 시작 (num[0]은 결과의 시작값으로 고정)
dfs(1, num[0])
print(maxV)
print(minV)

index : num 배열에서 현재 몇 번째 숫자를 사용할지

current : 지금까지 계산된 결과값

코드 설명

• num[0]을 시작값으로 잡고 DFS를 호출
• num[1]부터 하나씩 꺼내면서 남은 연산자를 하나씩 조합해봄
• 연산자가 하나 쓰일 때마다 ops[i] -= 1 (백트래킹)
• index == N까지 도달하면 결과값을 최댓값/최솟값으로 갱신

사용 알고리즘 정리

포인트	설명
DFS	숫자 순서대로 재귀 호출하면서 연산자를 적용
백트래킹	연산자 수를 원상복구해서 다른 경우도 탐색
나눗셈	음수일 경우 처리 방식에 주의 (-(-x // y))
초기값	maxV = -inf, minV = inf로 초기화