PS/Python
[Python] 백준(BOJ) 14888번: 연산자 끼워넣기
yoo.o
2020. 11. 5. 03:52
반응형
문제
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
풀이
순서가 중요하기 때문에 순열을 통해 구해줬고, 브루트포스로 다 계산해보며 최대값, 최소값을 구했다.
순열에 set을 안쓰면 시간초과가 나는걸 보니 테스트케이스중 중복이 큰게 있나보다
import sys
from itertools import permutations
# 수의 개수
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split(" ")))
op = list(map(int, sys.stdin.readline().split(" ")))
ops = []
for i in range(4):
for k in range(op[i]):
ops.append(i)
minimum = sys.maxsize
maximum = -1 * sys.maxsize
for com in set(permutations(ops, N-1)):
answer = A[0]
for i in range(len(com)):
if com[i] == 0:
answer += A[i+1]
elif com[i] == 1:
answer -= A[i+1]
elif com[i] == 2:
answer *= A[i+1]
else:
# 둘이 부호가 다르면
if answer * A[i+1] < 0:
answer = -1 * (abs(answer) // abs(A[i+1]))
else:
answer = answer//A[i+1]
minimum = min(minimum, answer)
maximum = max(maximum, answer)
print(maximum)
print(minimum)
반응형