[백준/파이썬]14888 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

문제

백준 14888번 연산자 끼워넣기

 

좀 어려웠던 백트레킹 문제다.

 

그러나 백트레킹 문제답게 넉넉한 시간, 넉넉한 메모리이 주어진다. 이는 효율성은 죽 쒀서 개 줘도 정답이 나올 가능성이 높다. 그래서 정답 비율이 높은 듯하다.

 

숫자들은 앞에서부터 차례대로 계산하면 되니 내버려두고 연산자만 모든 경우의 순열을 구하면 된다고 이해했다.

 

문제를 다 풀고 질문게시판 가보니 연산자 개수자체로 문제를 푸는 사람들도 있었지만 난 그런 생각은 1도 못했다.

 

나는 일단 입력받은 연산자 개수를 리스트로 만들어 주는 코드를 작성했다.

 

ex)

2 1 1 1

가 연산자의 개수라면

['+', '+', '-', '*', '//']

와 같이 리스트로 만들어 줬다.

 

그 후에 위에서 만든 리스트를 재귀로 모든 순열을 구해주면 된다.

 

이렇게 만든 알고리즘에 예제 입력 3을 입력하게 되면

 

['+', '+', '-', '*', '//']

1

['+', '+', '-', '*', '//']

0

['+', '+', '-', '//', '*']

3

['+', '+', '*', '-', '//']

-2

['+', '+', '*', '//', '-']

-24

['+', '+', '//', '-', '*']

-1

['+', '+', '//', '*', '-']

3

['+', '-', '+', '*', '//']

0

['+', '-', '+', '//', '*']

0

['+', '-', '*', '+', '//']

6

['+', '-', '*', '//', '+']

30

['+', '-', '//', '+', '*']

6

['+', '-', '//', '*', '+']

1

['+', '*', '+', '-', '//']

-4

['+', '*', '+', '//', '-']

1

['+', '*', '-', '+', '//']

7

['+', '*', '-', '//', '+']

1

['+', '*', '//', '+', '-']

3

['+', '*', '//', '-', '+']

0

['+', '//', '+', '-', '*']

19

['+', '//', '+', '*', '-']

12

['+', '//', '-', '+', '*']

-9

['+', '//', '-', '*', '+']

3

['+', '//', '*', '+', '-']

5

['+', '//', '*', '-', '+']

1

['+', '+', '-', '*', '//']

0

['+', '+', '-', '//', '*']

3

['+', '+', '*', '-', '//']

-2

['+', '+', '*', '//', '-']

-24

['+', '+', '//', '-', '*']

-1

['+', '+', '//', '*', '-']

3

['+', '-', '+', '*', '//']

0

['+', '-', '+', '//', '*']

0

['+', '-', '*', '+', '//']

6

['+', '-', '*', '//', '+']

30

['+', '-', '//', '+', '*']

6

['+', '-', '//', '*', '+']

1

['+', '*', '+', '-', '//']

-4

['+', '*', '+', '//', '-']

1

['+', '*', '-', '+', '//']

7

['+', '*', '-', '//', '+']

1

['+', '*', '//', '+', '-']

3

['+', '*', '//', '-', '+']

0

['+', '//', '+', '-', '*']

19

['+', '//', '+', '*', '-']

12

['+', '//', '-', '+', '*']

-9

['+', '//', '-', '*', '+']

3

['+', '//', '*', '+', '-']

5

['+', '//', '*', '-', '+']

5

['-', '+', '+', '*', '//']

6

['-', '+', '+', '//', '*']

2

['-', '+', '*', '+', '//']

7

['-', '+', '*', '//', '+']

30

['-', '+', '//', '+', '*']

6

['-', '+', '//', '*', '+']

5

['-', '+', '+', '*', '//']

6

['-', '+', '+', '//', '*']

2

['-', '+', '*', '+', '//']

7

['-', '+', '*', '//', '+']

30

['-', '+', '//', '+', '*']

6

['-', '+', '//', '*', '+']

1

['-', '*', '+', '+', '//']

6

['-', '*', '+', '//', '+']

1

['-', '*', '+', '+', '//']

6

['-', '*', '+', '//', '+']

10

['-', '*', '//', '+', '+']

10

['-', '*', '//', '+', '+']

48

['-', '//', '+', '+', '*']

21

['-', '//', '+', '*', '+']

48

['-', '//', '+', '+', '*']

21

['-', '//', '+', '*', '+']

7

['-', '//', '*', '+', '+']

7

['-', '//', '*', '+', '+']

0

['*', '+', '+', '-', '//']

-5

['*', '+', '+', '//', '-']

1

['*', '+', '-', '+', '//']

6

['*', '+', '-', '//', '+']

0

['*', '+', '//', '+', '-']

2

['*', '+', '//', '-', '+']

0

['*', '+', '+', '-', '//']

-5

['*', '+', '+', '//', '-']

1

['*', '+', '-', '+', '//']

6

['*', '+', '-', '//', '+']

0

['*', '+', '//', '+', '-']

2

['*', '+', '//', '-', '+']

1

['*', '-', '+', '+', '//']

6

['*', '-', '+', '//', '+']

1

['*', '-', '+', '+', '//']

6

['*', '-', '+', '//', '+']

10

['*', '-', '//', '+', '+']

10

['*', '-', '//', '+', '+']

3

['*', '//', '+', '+', '-']

5

['*', '//', '+', '-', '+']

3

['*', '//', '+', '+', '-']

5

['*', '//', '+', '-', '+']

7

['*', '//', '-', '+', '+']

7

['*', '//', '-', '+', '+']

12

['//', '+', '+', '-', '*']

29

['//', '+', '+', '*', '-']

24

['//', '+', '-', '+', '*']

1

['//', '+', '-', '*', '+']

11

['//', '+', '*', '+', '-']

13

['//', '+', '*', '-', '+']

12

['//', '+', '+', '-', '*']

29

['//', '+', '+', '*', '-']

24

['//', '+', '-', '+', '*']

1

['//', '+', '-', '*', '+']

11

['//', '+', '*', '+', '-']

13

['//', '+', '*', '-', '+']

36

['//', '-', '+', '+', '*']

11

['//', '-', '+', '*', '+']

36

['//', '-', '+', '+', '*']

11

['//', '-', '+', '*', '+']

-1

['//', '-', '*', '+', '+']

-1

['//', '-', '*', '+', '+']

3

['//', '*', '+', '+', '-']

5

['//', '*', '+', '-', '+']

3

['//', '*', '+', '+', '-']

5

['//', '*', '+', '-', '+']

7

['//', '*', '-', '+', '+']

7

['//', '*', '-', '+', '+']

 

이런 값들을 받을 수 있다. (첫째줄이 만들어진 순열로 계산했을 때의 값, 두 번째 줄이 만들어진 순열이다.)

 

그리고 이 문제를 풀 때 한 가지 주의할 점이 있는데, 문제에서 

 

음수를 양수로 나눌 때는 C++14의 기준을 따른다.

 

라고 되어 있다. 이는 파이썬에서 그냥 // 쓰면 안 된다.

 

c++ 음수 나누기 양수

c++ 14에서 -1 / 3은 0 이 출력되지만

파이썬 음수 나누기 양수

파이썬에서 -1 // 3은 -1이 출력된다.

 

따라서 사진과 같이 int(-1/3)처럼 /와 int함수를 사용해야 한다.

 

정답

def dfs(deep, oper_arr, v) :
    global min_, max_

    if deep == n-1 :
        if v > max_ :
            max_ = v
        if v < min_ :
            min_ = v
        return

    for i in range(len(oper_arr)) :
        new_arr = oper_arr[:i]+oper_arr[i+1:]
        if oper_arr[i] == '+' :
            dfs(deep+1, new_arr, v+num_arr[deep+1])
        elif oper_arr[i] == '-' :
            dfs(deep+1, new_arr, v-num_arr[deep+1])
        elif oper_arr[i] == '*' :
            dfs(deep+1, new_arr, v*num_arr[deep+1])
        elif oper_arr[i] == '//' :
            dfs(deep+1, new_arr, int(v/num_arr[deep+1]))


n = int(input())
num_arr = list(map(int, input().split()))
arr = list(map(int, input().split()))

operator_arr = []

for i in range(4) :
    for j in range(arr[i]) :
        if i == 0 :
            operator_arr.append('+')
        elif i == 1 :
            operator_arr.append('-')
        elif i == 2 :
            operator_arr.append('*')
        else :
            operator_arr.append('//')

min_ = 1000000001
max_ = -1000000001

dfs(0, operator_arr, num_arr[0])
print(max_)
print(min_)

---

채점하는데 2분 넘게 걸렸지롱