파이썬으로 풀어보는 백준 14888번: 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

내 풀이:

N = int(input())
sequence = list(map(int, input().split()))
operator = list(map(int, input().split()))
max_num = -1000000000
min_num = 1000000000
 
def go(index, operator, last):
    global max_num, min_num
    if index == N:
        if last > max_num:
            max_num = last
        if last < min_num:
            min_num = last
        return
 
    if operator[0] != 0:
        last += sequence[index]
        operator[0] -= 1
        go(index+1, operator, last)
        last -= sequence[index]
        operator[0] += 1
 
    if operator[1] != 0:
        last -= sequence[index]
        operator[1] -= 1
        go(index+1, operator, last)
        last += sequence[index]
        operator[1] += 1
 
    if operator[2] != 0:
        last *= sequence[index]
        operator[2] -= 1
        go(index+1, operator, last)
        last //= sequence[index]
        operator[2] += 1
 
    if operator[3] != 0:
        save = last
        last = int(last / sequence[index])
        operator[3] -= 1
        go(index+1, operator, last)
        last = save
        operator[3] += 1
 
go(1, operator, sequence[0])
print(max_num)
print(min_num)

Python3, 88ms

문제 조건에 따라 max값과 min값을 각각 -10억, +10억으로 설정한 후 각각의 조건에 해당하면 값을 바꾸도록 했다. 재귀적으로 푸는 방법을 택했기 때문에 모든 경우의 수에 대해서 계산한다. 마지막에 operator[3]에 대해서만 나눗셈이 조건문중에서는 마지막이기 때문에 원래의 값으로 되돌리는 행위를 하지 않았는데 이유는 모르겠으나 이 때문에 샘플 하나에 대해서 계속해서 다른 결과값을 보였기 때문에 문제를 푸는 데 다소 시간이 오래 소요되었다. 이에 대한 고찰은 좀 더 생각해 보아야 할 것 같다.