[백준 문제] 14888번 연산자 끼워넣기 (파이썬)
# 방법 1 : MAX, MIN으로
# 1. 다음 순열 구하는 함수
def next_permutation(a):
n = len(a) - 1
i = n
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i == 0:
return False
j = n
while a[i-1] >= a[j]:
j -= 1
a[i-1], a[j] = a[j], a[i-1]
j = n
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
return True
# 2. 연산자를 +는 0, -는, 1 *는 2, /는 3으로
def operation(a, b, x) :
if x == 0 :
return a+b
elif x == 1 :
return a-b
elif x == 2 :
return a*b
elif x == 3 :
if a < 0 :
a = -a
return -(a//b)
else :
return a//b
# 3. 입력
n = int(input())
a = list(map(int, input().split()))
oper = list(map(int, input().split()))
perm = [0]*oper[0]+[1]*oper[1]+[2]*oper[2]+[3]*oper[3]
#4. Max Min 구하기
arr = []
while True :
# summ구하기
summ = a[0]
for i in range(n-1) :
summ = operation(summ, a[i+1], perm[i])
arr.append(summ)
if next_permutation(perm) is False :
break
print(max(arr))
print(min(arr))
6
1 2 3 4 5 6
2 1 1 1
54
-24
# 방법 2 : MAX, MIN이 안먹힐때.
def next_permutation(a):
n = len(a) - 1
i = n
while i > 0 and a[i-1] >= a[i]:
i -= 1
if i == 0:
return False
j = n
while a[i-1] >= a[j]:
j -= 1
a[i-1], a[j] = a[j], a[i-1]
j = n
while i < j:
a[i], a[j] = a[j], a[i]
i += 1
j -= 1
return True
def operation(a, b, x) :
if x == 0 :
return a+b
elif x == 1 :
return a-b
elif x == 2 :
return a*b
elif x == 3 :
if a < 0 :
a = -a
return -(a//b)
else :
return a//b
n = int(input())
a = list(map(int, input().split()))
oper = list(map(int, input().split()))
perm = [0]*oper[0]+[1]*oper[1]+[2]*oper[2]+[3]*oper[3]
arr = []
while True :
# summ구하기
summ = a[0]
for i in range(n-1) :
summ = operation(summ, a[i+1], perm[i])
arr.append(summ)
if next_permutation(perm) is False :
break
maxx = arr[0]
for i in range(len(arr)) :
if maxx < arr[i] :
maxx = arr[i]
minn = arr[0]
for i in range(len(arr)) :
if minn > arr[i] :
minn = arr[i]
print(maxx)
print(minn)
6
1 2 3 4 5 6
2 1 1 1
54
-24