본문으로 바로가기

백준 14888. 연산자 끼워넣기

N개의 수와 N-1개의 연산자가 주어졌을 때,

수 사이에 연산자를 끼워넣어서 만들 수 있는

식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기 (itertools.permutations를 활용한 방법)

github에서 코드 보기 (재귀를 활용한 방법)

문제 조건

1. 문제에서 명시한 C++14기준에 따라서, 음수를 양수로 나눌 때에는 음수를 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수로 바꾸어야 한다.(예제 3번이 틀릴 경우 이 조건 때문이다)

2. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.

3. 나눗셈은 정수 나눗셈으로 몫만 취한다.

문제 풀이

문제를 해결할 수 있는 두가지 방법을 아래에 정리해보도록 하겠다. 

두 방법 모두 식을 만들 수 있는 경우의 수를 모두 조합하여 나온 결과값을 비교하는 브루트포스 방식이다.

처음에는 첫번째 방법으로 문제를 풀어 해결했고, 두번째는, 나보다 시간이 훨씬 빠른 정답 코드를 참고해 이해한 후 다시 작성해 제출한 방법이다. 

첫번째 방법으로 itertools의 permutations를 활용하여 순서를 고려한 모든 경우의 수를 구해 최대값과 최소값을 계산한다.

permutations으로 구할 경우에 원소가 같더라도 다른 경우로 취급되기 때문에 중복된 케이스가 상당히 많다. ex)  ['+', '+', '+', '+'] 

따라서 이러한 중복을 제거하기 위해서 iterable한 객체를 set 객체에 넣어 중복을 제거해주었다.  

라이브러리를 사용하면 코드가 간단해지고 구현하기가 쉽지만,  채점에서 꽤나 시간이 걸렸다. 

두번째 방법, 재귀를 활용해 마찬가지로 모든 경우의 수를 고려하여 최대값과 최소값을 계산한다.

이 방법은 내가 라이브러리를 사용한 것보다 1/10배 정도 빠른 시간안에 문제를 해결할 수 있다.

이 코드를 이해하려면 int() 메소드는 소숫점 자리를 버림한다는 파이썬 int() 메소드의 특징과, 이 문제에서 주어진 연산자들은 모두다 활용되어야 한다는 점이다.

이 조건에 따라서, 연산자의 수가 어느하나라도 남아있을 경우에는 해당 연산자를 사용하도록 코드를 작성하였다.

하나의 연산자를 사용할 경우에는 다음 연산자 위치에서는 아직 사용하지 않고 남은 연산자가 있다면 모두 탐색하도록 코드가 짜여 있다. (그러기 위해서 if~else문이 아니라 if문으로 구성되어 있다.)

파이썬 코드 - itertools.permutaions 활용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from itertools import permutations
from collections import deque
import copy
import sys
 
def solve(n, num_list, operation_count_list):
    op = ['+''-''*'"//"]
    operation_list = []
    max = -sys.maxsize - 1
    min = sys.maxsize
    for i in range(4):
        operation = op[i]
        count = operation_count_list[i]
        temp = [operation]*count
        operation_list.extend(temp)
 
    # 중복 제거
    case_list = set(permutations(operation_list, n-1))
 
    for case in case_list:
        temp_list = deque(copy.deepcopy(num_list))
        idx = -1
        result = temp_list.popleft()
        while temp_list:
            idx += 1
            next_num = temp_list.popleft()
            current_op = case[idx]
 
            if current_op == '+':
                result += next_num
            elif current_op == '-':
                result -= next_num
            elif current_op == '*':
                result *= next_num
            else:
                if result < 0:
                    result = -(result)
                    result //= next_num
                    result = -(result)
                else:
                    result //= next_num
 
        if result < min:
            min = result
 
        if max < result:
            max = result
 
    return max, min
 
 
if __name__ == "__main__":
    n = int(input().strip())
    num_list = deque(list(map(int, input().strip().split())))
    operation_count_list = deque(list(map(int, input().strip().split())))
 
    max, min = solve(n, num_list, operation_count_list)
    print(max)
    print(min)
cs

파이썬 코드 - recursion 활용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import sys
input = sys.stdin.readline
 
def cal(num, idx, add, sub, multi, division):
    global n, maxv, minv
    if idx == n:
        maxv = max(num, maxv)
        minv = min(num, minv)
        return
    else:
        if add:
            cal(num + num_list[idx], idx + 1, add-1, sub, multi, division)
        if sub:
            cal(num - num_list[idx], idx + 1, add, sub-1, multi, division)
        if multi:
            cal(num * num_list[idx], idx + 1, add, sub, multi -1, division)
        if division:
            cal(int(num/num_list[idx]), idx + 1, add, sub, multi, division -1)
 
 
if __name__ == "__main__":
    maxv = -sys.maxsize - 1
    minv =  sys.maxsize
    n = int(input().strip()) # 숫자의 수
    num_list = list(map(int, input().strip().split()))
    a, b, c, d = map(int, input().strip().split())
    cal(num_list[0], 1, a, b, c, d)
    print(maxv)
    print(minv)
cs

# 백준 14888. 연산자 끼워넣기 #백준 14888 python #백준 14888 파이썬 #백준 연산자 끼워넣기 #14888 연산자 끼워넣기