문제

BOJ 14888: 연산자 끼워넣기 https://www.acmicpc.net/problem/14888

풀이

조건

• N개의 수로 이루어진 수열이 주어진다.
• 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다.
• 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.
• 나눗셈은 정수 나눗셈으로 몫만 취한다.
• 음수를 양수로 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.
• 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
  • 이 부분은 파이썬에서는 굳이 신경쓰지 않아도 된다.

풀이 순서

• 입력받은 연산자의 개수를 각각의 변수에 저장한다.
• DFS를 사용한다.
• N개의 깊이에 도달하면 최대, 최소를 구하고 재귀를 종료한다.
• 아직 목표 깊이에 도달하지 않았다면 가능한 연산자를 사용한 계산을 하고 다음 깊이로 넘어간다.

코드

Python

N = int(input())
# 숫자들 입력
numbers = list(map(int, input().split()))
# 연산자 개수 입력
add, sub, mul, div = map(int, input().split())

max_ = -1e9
min_ = 1e9


def dfs(i, now):
    global min_, max_, add, sub, mul, div

    # 1부터 시작해서 N이 되면
    if i == N:
        min_ = min(min_, now)
        max_ = max(max_, now)
        return

    if add > 0:
        add -= 1
        dfs(i + 1, now + numbers[i])
        add += 1
    if sub > 0:
        sub -= 1
        dfs(i + 1, now - numbers[i])
        sub += 1
    if mul > 0:
        mul -= 1
        dfs(i + 1, now * numbers[i])
        mul += 1
    if div > 0:
        div -= 1
        dfs(i + 1, int(now / numbers[i]))
        div += 1

dfs(1, numbers[0])

print(max_)
print(min_)

정리

• 풀고 보니 생각보다 쉬운 문제였는데 DFS가 아직 잘 안된다.