114. [삼성기출10]Python 백준 14888 번 연산자 끼워넣기 자세한 설명

안녕하세요 코딩하는 덕구입니다.

백준 14888 번 연산자 끼워넣기 입니다.

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

먼저 백준 14888 번 연산자 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

N = int(input())
A = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

Max = -1e9
Min = 1e9

def dfs(depth, num):
    global Max, Min, add, sub, mul, div
    depth += 1

    if depth == N:
        Max = max(num, Max)
        Min = min(num, Min)

    else:
        if add > 0:
            add -= 1
            dfs(depth, num + A[depth])
            add += 1

        if sub > 0:
            sub -= 1
            dfs(depth, num - A[depth])
            sub += 1

        if mul > 0:
            mul -= 1
            dfs(depth, num * A[depth])
            mul += 1

        if div > 0:
            div -= 1
            if num < 0:
                num *= -1
                dfs(depth, (num // A[depth]) * -1)
            else:
                dfs(depth, (num // A[depth]))
            div += 1


dfs(0, A[0])
print(Max)
print(Min)

 

문제 요약

연산자와 수열이 주어집니다.

연산자의 위치는 마음대로 변경 가능하고, 수열은 고정되어 있습니다.

이때 연산자를 이동시키며 얻을 수 있는 최대값과 최소값을 출력합니다.

 

문제 접근

모든 경우의 수를 시도해보면 됩니다.

이때 중복되는 수식은 다시 계산하지 않도록 한다면 효율적이게 해결할 수 있습니다.

dfs를 통해 구현해봅시다.

 

Python 코드 구현

 입력받을 숫자의 개수 N, 숫자들의 list A, 더하기, 빼기, 곱하기, 나누기의 개수 add, sub, mul, div를 입력받습니다.

N = int(input())
A = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

 

최대값, 최소값을 저장할 변수도 초기화 해줍니다.

Max = -1e9
Min = 1e9

e9 = 10^9입니다.

2e9 = 2*10^9

1e9 = 1*10^9 

 

이제 dfs를 통해 모든 경우를 계산해 봅시다.

dfs는 재귀적으로 반복되고, 반복될 때 마다 깊이가 1 씩 늘어납니다. 

def dfs(depth, num):
    global Max, Min, add, sub, mul, div
    depth += 1

 

만약 모든 연산을 마치면 Max, Min 값을 업데이트하고 종료합니다.

if depth == N:
    Max = max(num, Max)
    Min = min(num, Min)

 

아직 연산이 남아있으면 add, sub, mul, div 를 하나씩 줄입니다.

이때 A[depth](다음 숫자),  [연산 (+, -, /, *)], num(지금까지 계산한 식의 값)을 업데이트하며 dfs를 재귀적으로 실행시킵니다.

결국에 각각의 dfs들은 depth가 N이 되면 좀 전에 위에서 처럼

연산을 마치고 Max, Min을 업데이트 하게 됩니다. 

else:
    if add > 0:
        add -= 1
        dfs(depth, num + A[depth])
        add += 1

    if sub > 0:
        sub -= 1
        dfs(depth, num - A[depth])
        sub += 1

    if mul > 0:
        mul -= 1
        dfs(depth, num * A[depth])
        mul += 1

    if div > 0:
        div -= 1
        if num < 0:
            num *= -1
            dfs(depth, (num // A[depth]) * -1)
        else:
            dfs(depth, (num // A[depth]))
        div += 1

 

이제 dfs를 실행시키고 Max, Min 을 출력하면됩니다.

dfs(0, A[0])
print(Max)
print(Min)

 

파이썬 백준 14888 번 연산자 끼워넣기 최종 코드입니다. 

N = int(input())
A = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

Max = -1e9
Min = 1e9

def dfs(depth, num):
    global Max, Min, add, sub, mul, div
    depth += 1

    if depth == N:
        Max = max(num, Max)
        Min = min(num, Min)

    else:
        if add > 0:
            add -= 1
            dfs(depth, num + A[depth])
            add += 1

        if sub > 0:
            sub -= 1
            dfs(depth, num - A[depth])
            sub += 1

        if mul > 0:
            mul -= 1
            dfs(depth, num * A[depth])
            mul += 1

        if div > 0:
            div -= 1
            if num < 0:
                num *= -1
                dfs(depth, (num // A[depth]) * -1)
            else:
                dfs(depth, (num // A[depth]))
            div += 1


dfs(0, A[0])
print(Max)
print(Min)

 

백준 14888 번 연산자 자세한 설명 및 Python 코드였습니다.

감사합니다.