[Python] 백준 14888번 : 연산자 끼워넣기

문제

14888번: 연산자 끼워넣기

[ 문제 조건 ]

• 입력
  1. N : 수의 개수
  2. A1 ~ An : 수들
  3. sum(N-1) : 합이 N-1인 4개의 정수, 연산자 4개의 각각 개수가 주어짐 (+,-,×,÷) 순으로
• 출력
  • 만들 수 있는 식의 최대 & 최소 값 출력
  • -10억 ≤ 결과값 ≤ 10억

[ 해결순서 ]

1. 백트래킹 유형은 dfs를 주로 사용하는 것 같아 dfs로 풀어보려고 했다.
2. 모든 경우의 수를 전부 구해 최대 최소를 비교하는 문제여서 어쨌든 모두 비교해서 구해야한다.
3. 1. 처음 먼저 plus가 1이니까 dfs가 걸려 깊이우선탐색 후 나머지 연산까지 깊이우선탐색 해 값을 갱신
   2. 깊이우선탐색 plus 연산은 끝났고, 나머지 연산 중 multiply 값이 1이므로 해당 연산 기준으로 재귀적으로 dfs 진행 후
   3. 최대, 최소 갱신 후 최종 갱신된 값이 정답이 될 것이다.예제 2를 분석해서 구해봤다.

[ 점화식 ]

dfs(depth+1, result+values[depth], plus, minus, multiply, divide)

✏️한줄평

: 생각한 대로 코드 짜기는 어렵다ㅜㅜ

---

코드

	n = int(input())
	values = list(map(int,input().split()))
	op = list(map(int,input().split()))
	max_val = -1e9
	min_val = 1e9
	def dfs(depth, result, plus, minus, multiply, divide):
	global max_val, min_val
	if depth == n:
	max_val = max(result, max_val)
	min_val = min(result, min_val)
	return
	if plus:
	dfs(depth+1, result+values[depth], plus-1, minus, multiply, divide)
	if minus:
	dfs(depth+1, result-values[depth], plus, minus-1, multiply, divide)
	if multiply:
	dfs(depth+1, result*values[depth], plus, minus, multiply-1, divide)
	if divide:
	if result < 0: #음수라면
	dfs(depth+1, -(-(result)//values[depth]), plus, minus, multiply, divide-1)
	else:
	dfs(depth+1, result//values[depth] , plus, minus, multiply, divide-1)
	dfs(1, values[0], op[0], op[1], op[2], op[3])
	print(max_val)
	print(min_val)

view raw BOJ14888.py hosted with ❤ by GitHub