cho.sh

연산자 끼워넣기 (2)

주어진 연산자 공급에서 인접한 수 사이마다 하나씩 넣어 왼쪽부터 계산하고, C++14 정수 나눗셈을 적용해 만들 수 있는 식의 최댓값과 최솟값을 구한다.

보통6백트래킹완전 탐색구현재귀면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

NN개의 수로 이루어진 수열 A1,A2,…,ANA_1, A_2, \dots, A_N과, 수와 수 사이에 끼워넣을 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷) 네 종류뿐이고, 개수는 N−1N-1보다 많을 수도 있다. 모든 수 사이에는 연산자를 한 개씩 끼워넣어야 하지만, 주어진 연산자를 모두 쓸 필요는 없다.

수와 수 사이에 연산자를 하나씩 넣으면 수식 하나가 만들어진다. 이때 수의 순서는 바꿀 수 없다.

수열이 1, 2, 3, 4, 5, 6이고 연산자가 덧셈 3개, 뺄셈 2개, 곱셈 1개, 나눗셈 1개면 만들 수 있는 식은 모두 250가지다. 그중 여섯 개를 적으면 다음과 같다.

  • 1+2+3−4×5÷61+2+3-4 \times 5 \div 6
  • 1÷2+3+4−5×61 \div 2+3+4-5 \times 6
  • 1+2÷3×4−5+61+2 \div 3 \times 4-5+6
  • 1÷2×3−4+5+61 \div 2 \times 3-4+5+6
  • 1+2+3+4−5−61+2+3+4-5-6
  • 1+2+3−4−5×61+2+3-4-5 \times 6

식은 연산자 우선순위를 무시하고 앞에서부터 차례대로 계산한다. 나눗셈은 몫만 취하는 정수 나눗셈이고, 음수를 양수로 나눌 때는 C++14의 규칙을 따른다. 즉 음수를 양수로 바꿔 몫을 구한 다음, 그 몫의 부호를 다시 음수로 바꾼다. 위 여섯 식을 계산한 결과는 다음과 같다.

  • 1+2+3−4×5÷6=11+2+3-4 \times 5 \div 6 = 1
  • 1÷2+3+4−5×6=121 \div 2+3+4-5 \times 6 = 12
  • 1+2÷3×4−5+6=51+2 \div 3 \times 4-5+6 = 5
  • 1÷2×3−4+5+6=71 \div 2 \times 3-4+5+6 = 7
  • 1+2+3+4−5−6=−11+2+3+4-5-6 = -1
  • 1+2+3−4−5×6=−181+2+3-4-5 \times 6 = -18

수와 연산자가 주어지면 만들 수 있는 식의 결과 중 최댓값과 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 NN이 주어진다. (2≤N≤112 \le N \le 11)

둘째 줄에 A1,A2,…,ANA_1, A_2, \dots, A_N이 주어진다. (1≤Ai≤1001 \le A_i \le 100)

셋째 줄에 정수 네 개가 주어진다. 차례대로 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)의 개수이고, 네 수의 합은 N−1N-1보다 크거나 같고 4N4N보다 작거나 같다.

출력

첫째 줄에 만들 수 있는 식의 결과 중 최댓값을, 둘째 줄에 최솟값을 출력한다.

연산자를 어떻게 끼워넣어도 결과가 항상 -10억보다 크거나 같고 10억보다 작거나 같은 입력만 주어진다. 앞에서부터 계산하는 중간 결과도 항상 -10억보다 크거나 같고 10억보다 작거나 같다.

힌트

수열이 1, 2, 3, 4, 5, 6이고 연산자가 덧셈 3개, 뺄셈 2개, 곱셈 1개, 나눗셈 1개인 경우, 최댓값과 최솟값은 다음 두 식에서 나온다.

  • 최댓값: 1÷2+3+4+5×61 \div 2+3+4+5 \times 6
  • 최솟값: 1+2÷3−4−5×61+2 \div 3-4-5 \times 6