[백준 14888 ] 연산자 끼워넣기 (python 풀이)

1.문제 

N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.진다.

3. 출력

첫째 줄에 답을 출력한다

---

4. 포인트

1. max 값 min 값 하나씩을 구하는 것 이기 때문에 각각의 결과 값들을 저장할 필요가 없다 
   • global 변수를 통해 해결 : 글로벌 변수는 함수 안에서 생성하더라도 전역변수로 사용이 된다. 그러나 이때 함수안에서 초기화 할경우 recursive 하게 초기화 되기 때문에 밖에서 초기화 하고 안에서 사용하게 된다.
2.   if 문을 여럿 열거함으로서 백트레킹을 구현할 수 있다. 
   1. 백트래킹으로 리스트를 상용할경우 recursive 함수에 넣고 다시 복구해주는 것이 중요함

4. 문제 풀이

  본 문제는 백트래킹으로 풀 수 있다. 처음에는 0만들기를 풀었던 기억에 행렬로 만들었지만 굳이 그럴 필요가 없었다. 때에 따라서 단순 연산으로 풀지 리스트로 원소를 넣고 빼면서 풀지 잘 생각해보자. 특히 본 문제는 마지막 두 값만을 원하므로 단순 연산이 용이하다.

 백트래킹 구현은 복습을 통해 연습하자

# 연산자 끼워넣기
import copy
N = int(input())
lst = list(map(int , input().split()))
operList =  list(map(int , input().split()))

maximum = -1e9
minimum = 1e9
def recur( cnt , total , plus , minus , mul , div ):
    global maximum  , minimum
    if cnt == N:
        maximum = max(maximum , total)
        minimum = min (minimum ,total)
        return 

    if plus :
        recur(cnt+1 , total + lst[cnt] , plus-1 , minus , mul , div)
    if minus:
        recur(cnt + 1, total - lst[cnt], plus, minus - 1, mul, div)
    if mul:
        recur(cnt + 1, total * lst[cnt], plus, minus, mul - 1, div)
    if div:
        recur(cnt + 1, int(total / lst[cnt]), plus, minus, mul, div - 1)

recur(1, lst[0] , operList[0] , operList[1] , operList[2] , operList[3])
print(maximum)
print(minimum)