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

문제 링크

14888번: 연산자 끼워넣기

문제 설명

• 순서가 있는 N개의 숫자를 받고 그 숫자 사이에 N-1개의 연산자를 삽입하는 문제
• 중복을 허용하고, 4종류의 연산자로 이루어진 N-1 길이의 순열을 모두 탐색하는 방법으로 접근

고민 한 부분

•  DFS 방식으로 탐색을 하며 이미 탐색한 순열은 다시 탐색하지 않도록 가지치기할 방법 $line 39$

N-1 x 4 크기의 visited 배열을 활용해 depth 번째에 삽입 될 연산자가 이미 사용됐다면 탐색하지 않는 방식으로 탐색 영역을 줄임

 

	import sys, math, copy
	## 조합 문제 > backtracking
	min = math.inf
	max = -math.inf
	def cal$x, y, op$:
	if op == 0:
	r = x+y
	elif op == 1:
	r = x - y
	elif op == 2:
	r = x * y
	else :
	r = abs$x$ // y
	if x <0:
	r = -r
	return r
	def DFS$perm, depth = 0$:
	global max, min
	## 탈출조건
	if sum$num_operators$ == 0:
	result = numbers[0]
	for i in range$N-1$:
	result = cal$result, numbers[i+1],perm[i]$
	if result > max:
	max = result
	if result < min:
	min = result
	return
	for i in range$4$:
	# visit
	## visited -> 해당 depth에 같은 operator가 사용됐으면 가지치기
	if num_operators[i] >0 and visited[depth][i] == 0:
	num_operators[i] -= 1
	visited[depth][i] =1
	perm.append$i$
	# next node
	DFS$perm, depth + 1$
	# undo visit
	num_operators[i] += 1
	visited[depth][i] = 0
	perm.pop
	if __name__ == "__main__":
	turn_in = 0
	if turn_in == 0:
	sys.stdio = open$'test_case.txt'$
	N = int$sys.stdio.readline($)
	numbers = list$map(int, sys.stdio.readline($.split))
	num_operators = list$map(int, sys.stdio.readline($.split))
	# + - x /
	else:
	N = int$sys.stdin.readline($)
	numbers = list$map(int, sys.stdin.readline($.split))
	num_operators = list$map(int, sys.stdin.readline($.split))
	visited = [[0] * 4 for i in range$N$]
	perm = [] # 연산자 순서대로 받는 임시
	DFS$perm$
	print$max$
	print$min$

view raw boj_14888.py hosted with ❤ by GitHub

Lesson learned

max_ = max(max_, result)
min_ = min(min_, result)

• 최대, 최소값을 갱신할 때, python의 내장 함수 max, min을 사용해 코드 길이와 실수를 줄일 수 있음 $line 29~32$ 

from itertools import permutations

test_list = [1,2,3,4,5] # 순열을 만들 대상들
L = 3 # 만들 순열의 길이
perm_generator = permutations(test_list, L)

• python에 itertools 모듈에 permutations를 활용하면 list item으로 구성된 N 크기의 순열을 모두 생성하는 generator를 만들 수 있음. 이렇게 풀게되면 시간초과로 통과를 하지 못하지만 간단하기 때문에 먼저 시도해볼만 한 것 같음
• perm_generator를 for문에 사용하거나 next 함수를 사용해 요소를 하나씩 반환할 수도 있음