백준 14888번 연산자 끼워넣기
이코테 350p

문제

입출력

• 조건
  • 시간 2초 / 메모리 512MB
• 입력
  • 첫째줄 : 수의 갯수 N
    (2<=N<=11)
  • 둘째줄 : $A_1, A_2,...,A_N$
    (1<=$A_i$<=100)
  • 셋째줄 : 합이 N-1인 4개 정수.
    차례로 +갯수, -갯수, X 갯수, / 갯수
• 출력
  • 첫째줄 : 만들 수 있는 식의 결과의 최댓값
  • 둘째줄 : 최솟값
  • 모든 결과값과 중간값은 -10억보다 크거나 같음.

상황

최대 11개의 수가 주어졌을때, 각 수와 수 사이에 사친연산 중 하나를 삽입

풀이

• 모든 경우의 수를 시간 내에 계산할 수 있음을 보장할 수 있는가
• 모든 경우의 수 완전탐색의 방법으로 DFS/BFS를 적절히 사용할 수 있는가

풀이 아이디어

모든 경우의 수를 다 계산하는 방법으로,
간단한 선형적인 경우는 for문을 사용하지만
이런 케이스의 경우 DFS/BFS를 통해 모든 경우의 수를 계산(탐색)하는 것으로 쓸 수도 있다.

느낀점

아쥑 재귀를 통해서 모든 경우의 수를 확인한다다 는게
직관적으로 이해가 안됨 (?)
그래프 손으로 그려봐서 직접 눈으로 확인하고 익숙해집시다

코드

n = int(input())
# 연산 수행하고자 하는 수 리스트
data = list(map(int, input().split()))
# 더하기, 빼기, 곱하기, 나누기 연산자 갯수
add, sub, mul, div = map(int, input().split())

# 최솟값과 최댓값 초기화
min_value = 1e9
max_value = -1e9

# DFS 메서드
def dfs(i, now) :
	global min_value, max_value, add, sub, mul, div
	# 모든 연산자를 다 사용한 경우, 최솟값과 최댓값 업데이트
	if i == n :
		min_value = min(min_value, now)
		max_value = max(max_value, now)
	# 아닌 경우, 각 연산자에 대하여 재귀적으로 수행
	else :
		if add > 0 :
			add -= 1
			dfs(i+1, now+data[i])
			add += 1
		if sub > 0 :
			sub -= 1
			dfs(i+1, now-data[i])
			sub += 1
		if mul > 0 :
			mul -= 1
			dfs(i+1, now*data[i])
			mul += 1
		if div > 0 :
			div -= 1
			dfs(i+1, int(now/data[i])) # 나눌때 나머지 제거
			div += 1

dfs(1, data[0])

print(max_value)
print(min_value)