[백준 문제] 14888번 연산자 끼워넣기 (파이썬)


[백준 문제] 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





© 2018. by statssy

Powered by statssy