백준 14888: 연산자 끼워넣기 Python (순열, DFS)

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

14888번: 연산자 끼워넣기

 

 

이 문제는 지문을 잘 읽어야 하는데, 우선 숫자의 순서는 변경하면 안된다.

문제를 보자마자 떠오른 방법은 순열이었는데 위 조건을 미처 보지 못해서 계속해서 헤맸다.

두 번째로 주의해야 할 것은 음수일 때 나눗셈을 하는 경우이다.

print(-6 // 2)를 했더니 -3으로 결과가 잘 나오길래 따로 조건을 달아주지 않았었는데, 그렇게 하면 예시3에서 최댓값이 틀리게 된다.

1. 순열 (라이브러리x)

N = int(input())    # N: 수의 개수
nums = list(map(int, input().split()))  # nums: 수 배열
multi = list(map(int, input().split()))     # multi: 연산자 (+, -, *, //)

# 연산자 리스트 만들기
operator = []
for i in range(4):
    for j in range(multi[i]):
        if i == 0:
            operator.append('+')
        elif i == 1:
            operator.append('-')
        elif i == 2:
            operator.append('*')
        else:
            operator.append('//')


# 연산자 순열
def op_perm(n, k):
    if n == k:
        result = nums[0]
        for m in range(n):
            if operator[m] == '+':
                result += nums[m + 1]
            elif operator[m] == '-':
                result -= nums[m + 1]
            elif operator[m] == '*':
                result *= nums[m + 1]
            elif operator[m] == '//':
                if result < 0:
                    result = (result * (-1) // nums[m+1]) * (-1)
                else:
                    result //= nums[m + 1]
        result_list.append(result)
    else:
        for l in range(k, n):
            operator[l], operator[k] = operator[k], operator[l]
            op_perm(n, k+1)
            operator[l], operator[k] = operator[k], operator[l]


result_list = []
op_perm(len(operator), 0)
print(max(result_list))
print(min(result_list))

코딩테스트를 치다보면 라이브러리를 사용하지 못하게 하는 경우도 있어서, 되도록이면 순열 또는 조합을 라이브러리 없이 구현하는 연습을 하려고 노력한다.

위 방법은 재귀를 이용한 방법인데, 이렇게 하면 Python3에서는 시간 초과가 나고 PyPy로 해야 겨우 통과한다.

하지만 메모리는 223236KB, 시간은 2144ms로 매우 효율이 떨어진다.

 

 

2. DFS

N = int(input())    # N: 수의 개수
nums = list(map(int, input().split()))  # nums: 수 배열
operator = list(map(int, input().split()))     # multi: 연산자 (+, -, *, //)


def dfs(n, k, total, plus, minus, multi, divide):
    if n == k:
        result_list.append(total)
        return
    else:
        if plus:
            dfs(n, k + 1, total + nums[k], plus-1, minus, multi, divide)
        if minus:
            dfs(n, k + 1, total - nums[k], plus, minus-1, multi, divide)
        if multi:
            dfs(n, k + 1, total * nums[k], plus, minus, multi-1, divide)
        if divide:
            if total < 0:
                dfs(n, k + 1, (total * (-1) // nums[k]) * (-1), plus, minus, multi, divide - 1)
            else:
                dfs(n, k + 1, total // nums[k], plus, minus, multi, divide - 1)


result_list = []
dfs(N, 1, nums[0], operator[0], operator[1], operator[2], operator[3])
print(max(result_list))
print(min(result_list))

아래 블로그를 참고해서 dfs로 풀었다.

Python3로도 패스를 했고 메모리는 30840KB, 시간은 88ms가 나왔다.

 

참고

https://pacific-ocean.tistory.com/366