https://www.acmicpc.net/problem/14888
시간 2초, 메모리 512MB
input :
- N(2 ≤ N ≤ 11)
- A1, A2, ..., AN (1 ≤ Ai ≤ 100)
- 합이 N-1인 4개의 정수
output :
- 첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력
조건 :
-
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
-
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.
파이썬이 아닌 다른 언어를 사용한다면 우선 누적 합을 저장하는 변수는 long long이 되지 않아도 된다. 계산의 결과가 10억을 넘지 않는다고 하니 그냥 정수형으로도 충분하다.
문제의 조건에서 수의 순서가 바뀌면 안 된다고 한다. 그러면 모든 경우를 확인해야 하는 건데 모든 경우를 확인한다고 할 때 최대 연산자의 개수는 10개이다.
이걸 재귀의 방식으로 한다면? 충분히 가능할 것이다.
사실 그냥 구현의 문제인거 같다. 재귀의 방식에서 연산자의 수를 빼주면서 확인한 후에 그 이후에는 그 다음 연산자를 사용하고 살짝 DSLR문제를 해결하는 방식을 사용하면 된다.
그리고 나눗셈의 경우에는 조건을 살려서 계산하여 준다.
import sys
sys.setrecursionlimit(100000)
def make(val, idx):
global max_val, min_val
if idx == n:
max_val = max(max_val, val)
min_val = min(min_val, val)
return
if oper[0] != 0:
oper[0] -= 1
make(val + data[idx], idx + 1)
oper[0] += 1
if oper[1] != 0:
oper[1] -= 1
make(val - data[idx], idx + 1)
oper[1] += 1
if oper[2] != 0:
oper[2] -= 1
make(val * data[idx], idx + 1)
oper[2] += 1
if oper[3] != 0:
oper[3] -= 1
if val < 0:
val = -val
make(-(val // data[idx]), idx + 1)
else:
make(val // data[idx], idx + 1)
oper[3] += 1
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
oper = list(map(int, sys.stdin.readline().split()))
max_val, min_val = -float('inf'), float('inf')
make(data[0], 1)
print(max_val)
print(min_val)
