[Python] 백준 14888 연산자 끼워넣기,

문제

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

 

풀이 방식

해당 문제는 연산자를 사용하며, 가능한 연산을 모두 해보는 완전탐색과 백트래킹으로 해결할 수 있다.

 

문제를 해결하기 위해서 각 연산을 수행하고, 재귀구조로 이를 구현했다.

덧셈, 뺄셈, 곱셈, 나눗셈에 대한 모든 연산을 수행할 수 있도록 dfs함수 내에 for문으로 각 연산을 수행했다.

 

이렇게 간단하게 해결할 수 있는데, 파이썬의 경우 3번 케이스에서 문제가 발생한다.

 

본 문제에서 연산자의 숫자는 들어온 순서대로 진행하며, 나눗셈은 버림 연산을 한다고 명시되어 있다.

여기서, 나눗셈의 버림 연산 과정이 문제이다.

 

파이썬에서 나눗셈의 몫만 사용하는 연산은 // 인데, 문제 발생은 이 연산자의 작동 방식에 있다.

Python의 나눗셈 //은 음수를 내림(버림) 하기 때문에, 음수 나눗셈 과정이 제대로 구현되지 않기 때문이다.

이를 해결하기 위해서, 나눗셈 연산하는 과정에서 음수는 양수로 변환해서 처리하고, 그 결과에 음수를 달아줘야 한다.

 

if result < 0:
    tmp = -(-result // num[cur])
else:
    tmp = result // num[cur]

 

위 방식으로 나눗셈을 구현하고, 나머지는 동일하게 해주면 쉽게 해결할 수 있다.

코드

def dfs(cur, oper, result):
    if sum(oper) == 0:
        ans.add(result)
        return
    
    for i, op in enumerate(oper):
        if op == 0:
            continue
        
        # 연산이 가능하면, 연산 추가해서 실행
        if i == 0: # 덧셈
            tmp = result + num[cur]
        elif i == 1: # 뺄셈
            tmp = result - num[cur]
        elif i == 2: # 곱셈
            tmp = result * num[cur]
        else: # 나눗셈
            if result < 0:
                tmp = -(-result // num[cur])
            else:
                tmp = result // num[cur]

        oper[i] -= 1
        dfs(cur+1, oper, tmp)
        oper[i] += 1

n = int(input())
num = list(map(int, input().split()))
operators = list(map(int, input().split()))
ans = set()

dfs(1, operators, num[0])

print(max(ans))
print(min(ans))