[Baekjoon]백준 14888 연산자 끼워넣기(실버 1) - Python

문제설명 1

문제설명 2

힌트

이번 문제는 삼성 SW 역량 테스트 기출 문제인 백트래킹 알고리즘 문제이다

첫 줄에 입력받은 수만큼 숫자를 입력받고 연산자의 개수를 입력받은 후에 계산 결과의 최솟값과 최댓값을 구해야한다

대신 원래의 식처럼 우선순위가 있는 것이 아닌 앞에서부터 순서대로 계산하면 되는 문제이다

그렇기 때문에 백트래킹 알고리즘으로 해결이 가능하다

 

최댓값과 최솟값에 대한 범위가 주어져있기 때문에 -10억과 10억으로 최댓값과 최솟값을 각각 초기화해준다

이후에 백트래킹 알고리즘을 작성하는 부분이 항상 막히게 된다

일단 초반 if문을 통해 주어진 수만큼 함수를 실행하였다면 종료하는 부분을 만든 후에 고민을 하였다

연산자를 입력받을 때 리스트로 입력을 받았기 때문에 각각 if문을 통해 구분을 하여 계산을 시도하였다

 

if operator[0]: 과 같은 부분을 네 개 만들어주고 if문에 들어오면 해당 연산자를 사용하였다는 뜻이므로  -1을 해주어야한다

이후 solve()함수를 재귀적으로 호출하고, 호출한 후에는 다시 +1을 해주어서 백트래킹 알고리즘을 완성해준다

이를 모든 연산자(operator[0], operator[1], operator[2], operator[3])에 동일하게 작성하되, 

각 연산자마다 역할이 다르기 때문에 인자를 전달할 때는 각각 다르게 작성하여야한다

여기서 주의할 점은 나눗셈인데, 나누기를 할 때 python에서는 -6 // 4 를 하면 -2가 출력된다

그렇기 때문에 나누어지는 수와 나누는 수 중에서 하나라도 음수라면 절댓값 함수를 통해 계산해주어야한다

초반에 solve함수를 호출할 때에는 num[0]을 초기값으로 설정하기 위해 인자로 1과 num[0]을 넣어주면 된다

이후에 max_value, min_value를 각각 출력해주면 끝이다

def solve(n, result):
    global max_value
    global min_value
    if n == N:
        max_value = max(max_value, result)
        min_value = min(min_value, result)
        return
    else:
        if operator[0]:
            operator[0] -= 1
            solve(n + 1, result + num[n])
            operator[0] += 1
        if operator[1]:
            operator[1] -= 1
            solve(n + 1, result - num[n])
            operator[1] += 1
        if operator[2]:
            operator[2] -= 1
            solve(n + 1, result * num[n])
            operator[2] += 1
        if operator[3]:
            operator[3] -= 1
            if result < 0 or num[n] < 0:
                solve(n + 1, -(abs(result) // abs(num[n])))
            else:
                solve(n + 1, result // num[n])
            operator[3] += 1
        
N = int(input())
num = list(map(int, input().split()))
operator = list(map(int, input().split()))
max_value, min_value = -1000000000, 1000000000

solve(1, num[0])
print(max_value)
print(min_value)

pypy3와 python제출 결과