boj 14888 연산자 끼워넣기 (python)

어려...어려워

다른 분들은 어떨지 모르겠지만

dfs 배운지가 언제더라... 굴려라 맷돌!

 

지금껏 게을리 공부하던 날 머쓱해하며 계속 하면 나아지겠지

암튼 (〃⌒▽⌒〃)ゝ

 

 

조건_

1. 연산자 우선순위를 무시하고 앞에서부터 계산을 진행한다.

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

3. 음수를 양수로 나눌 때는 C++14의 기준을 따라, 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수롤 바꾼다. 

 

구해야 하는 것_

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것의 값 출력

 

 

풀이_

크게 두 가지 방법이 있다. (둘 다 전수조사이다)

첫번째, 순열을 사용하여

두번째, DFS를 사용하여 모든 경우의 수를 구해보는 것. (백트레킹)

 

*백트레킹(Backtracking) : 모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방법. 일종의 트리 탐색 알고리즘이다. 

 

순열은 itertools를 import하여 itertools.permutation(n,r)로 사용할 수 있다.

근데 나는 시간초과가 나서 dfs를 쓰기로 했다.

 

DFS 깊이 우선 탐색을 하게되면 재귀함수를 사용할 수 있다. 

 

아래 코드를 보면 깊이와 연산자 개수를 이용하여 재귀를 진행하게 된다. 

import sys
N = int(input())
operand = list(map(int, input().split()))
operator = list(map(int, input().split()))

maxnum = -sys.maxsize - 1
minnum = sys.maxsize

def dfs(depth, total, plus, minus, multiply, divide):
    print(total)
    global maxnum, minnum
    if depth == N:
        maxnum = max(total, maxnum)
        minnum = min(total, minnum)
        
    if plus:
        print('run plus')
        dfs(depth + 1, total + operand[depth], plus - 1, minus, multiply, divide)
    if minus:
        dfs(depth + 1, total - operand[depth], plus, minus - 1, multiply, divide)
    if multiply:
        print('run mul')
        dfs(depth + 1, total * operand[depth], plus, minus, multiply - 1, divide)
    if divide:
        dfs(depth + 1, int(total / operand[depth]), plus, minus, multiply, divide - 1)


dfs(1, operand[0], operator[0], operator[1], operator[2], operator[3])
print(maxnum)
print(minnum)

이렇게 코드만 보면 어떻게 돌아가고 있는지 파악이 안 될때가 있다.

 

그래서 예제 코드로 한 번 살펴보면

N = 3

operand = [ 3, 4, 5 ]

operator = [ 1, 0, 1, 0 ]

이렇게 입력받았을 때

 

맨 처음 더하기 부분이 1이므로 if plus: ~ 가 돌아가게 된다.

3 + 4 = 7

 

plus - 1 되었으므로 0이 되고 다음으로 1인 곱하기가 돌아가게 된다. 

if plus ( if multi )  <- 현재 이런 상황이다.

7 * 5 = 35

 

if plus ( if multi (if depth == N ))

35는 maxnum이 되고

if plus ( if multi ) // if depth == N 종료

if plus // if multi 종료

if plus 도 종료 그리고 다음 코드인 if minus로 넘어간다.

근데 minus는 0이니까 multiply로 가서 앞과 같은 과정 진행 ....