[백준] 14888 연산자 우선순위 python - 구현, 백트래킹

문제링크:https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

예제 입력:
2
5 6
0 0 1 0

예제 출력:
30
30

---

문제유형: 백트래킹, 구현, DFS

풀이

사칙연산의 모든 경우를 탐색하여 최댓값과 최솟값을 구하는 문제이다.
문제에서 구하고자 하는 것은 주어진 사칙연산을 이용하여 만들 수 있는 모든 결괏값 중 최대와 최소이다.(output)
풀이하며 엄청 헤맸던 문제 중 하나이다.. 단순히 for 문과 if 문을 사용해서 코드를 작성하려 했지만 방법을 찾지 못했고 다른 사람들이 풀어놓은 코드를 참고해서 겨우 제출했다.

* for, if 만으로 작성했다고 하더라도 출력 조건 때문에 터지지 않았을까 의심된다(확실치 않음)

 

상세 설명:

#사칙연산 수행 함수
def func(add, sub, mul, div, res = 0, i = 0):

덧셈을 사용할 수 있는 경우(add>0), 기호 개수에서 1을 뺀 값(add-1, sub, mul, div)을 func 함수의 인자로 넘겨준다. 이 때, res에 현재까지 계산된 결과 값(덧셈:res+A[i])을 더해주고, 다음 사용할 숫자의 인덱스(i+1)를 넘겨준다.

    if add > 0:
    
    	#add를 1 감소시키고
        func(add - 1, sub, mul, div, res + A[i], i + 1)

이렇게 계속해서 함수를 호출하다가, 모든 기호의 개수가 0이 되면 결과 값을 answer 리스트에 추가한다.

	#모든 기호의 개수가 0이 되면 함수를 종료한다.
    #예를 들어 add = 2 라면, 덧셈을 최대 2번 수행할 수 있음을 의미한다.
    if add == 0 and sub == 0 and mul == 0 and div == 0:
        answer.append(res)
        return

코드의 마지막 부분에서는, func 함수를 숫자 리스트 A의 첫 번째 숫자(A[0])와 함께 호출하여 모든 경우를 탐색한다.

func(add, sub, mul, div, A[0], 1)

 

정답 코드:

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())      #사칙연산 기호 개수 입력
answer = []

#res = 현재까지 계산된 결과값, i = 숫자 리스트 A에서 사용할 숫자의 개수
def func(add, sub, mul, div, res = 0, i = 0):
	
    #모든 기호가 0이 된 순간 = 모든 기호를 다 사용한 경우, 현재까지 계산된 결과값을 answer에 append하고 함수를 종료한다.
    if add == 0 and sub == 0 and mul == 0 and div == 0:
        answer.append(res)
        return

    if add > 0:     #덧셈
        func(add - 1, sub, mul, div, res + A[i], i + 1)
    if sub > 0:     #뺄셈
        func(add, sub - 1, mul, div, res - A[i], i + 1)
    if mul > 0:     #곱셈
        func(add, sub, mul - 1, div, res * A[i], i + 1)
    if div > 0:     #나눗셈
        if res > 0:
            func(add, sub, mul, div - 1, int(res / A[i]), i + 1)
        else:
            func(add, sub, mul, div - 1, -int(-res / A[i]), i + 1)

func(add, sub, mul, div, A[0], 1)
print(max(answer))
print(min(answer))