🥚문제

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

• 브루트포스 알고리즘
• 백트래킹

---

🥚입력/출력

---

🍳코드

def solve(x, op, i):
    global max_ans, min_ans
    if i == N:
        min_ans = min(min_ans, x)
        max_ans = max(max_ans, x)
        return

    # +
    if op[0] > 0:
        op[0] -= 1
        solve(x + A[i], op, i+1)
        op[0] += 1
    # -
    if op[1] > 0:
        op[1] -= 1
        solve(x - A[i], op, i+1)
        op[1] += 1
    # *
    if op[2] > 0:
        op[2] -= 1
        solve(x * A[i], op, i+1)
        op[2] += 1
    # /
    if op[3] > 0:
        op[3] -= 1
        if x < 0:
            result = -(-x // A[i])
            solve(result, op, i+1)
        else:
            solve(x // A[i], op, i+1)
        op[3] += 1


N = int(input())
A = list(map(int, input().split()))
# 0: +, 1:-, 2:*, 3:/
op = list(map(int, input().split()))
# 최대, 최소값 구하기
max_ans = -1000000000
min_ans = 1000000000
solve(A[0], op, 1)
print(max_ans)
print(min_ans)

---

🧂아이디어

구현

• 현재까지의 결과 x, 연산자의 개수를 저장하는 리스트 op, 다음 연산의 피연산자가 될 수열의 인덱스 i를 인자로 갖는 함수 solve를 작성했다.

• op[0] = 남은 + 연산자의 개수,
  op[1] = 남은 - 연산자의 개수,
  op[2] = 남은 * 연산자의 개수,
  op[3] = 남은 /(//) 연산자의 개수이다.

• 현재 결과가 x일 때, op[0]~op[3]을 확인하면서 0보다 큰 값이라면 x와 A[i]를 피연산자로, 해당 연산을 수행한 결과를 solve 함수의 인자로 넘긴다.
  • 예를 들어, 현재 x = 1일 때, op[0] > 0이라면 + 연산을 수행할 수 있다.
    op[0]-=1을 해서 + 연산자를 하나 소모했음을 표시하고
    solve(x + A[i], op, i+1)을 수행한다.
    이후 op[0] += 1을 하여 값을 복원한다 (백트래킹)

• 음수를 양수로 나눌 때 주의한다! 문제에서 설명한대로
  나눗셈은 정수 나눗셈으로 몫만 취하며,
  음수를 양수로 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼다.

• i의 값이 N일 때, x가 저장하고 있는 값은 계산식의 결과이다. 그 결과를 이용해 최대, 최소값을 갱신한다.