연산자 끼워넣기

 

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

문제요약:

말그대로 숫자와 연산자의 개수가 주어질 때 , (앞에서 부터 계산) 최대 최소값을 구하라

실버 1

 

소요시간:

25분

 

1차시도:

import sys
input = sys.stdin.readline
from itertools import permutations

n = int(input())
arr = list(map(int,input().split()))

giho = list(map(int,input().split()))
Giho = ['+','-','*','/']
Giho = ''.join([Giho[i] * giho[i] for i in range(4)])
max = -(1e11)
min = 1e11

for giho in set(list(permutations(Giho,len(Giho)))):
	result= arr[0]
	for i in range(n-1):
		if giho[i]== '+':
			result += arr[i+1]
		elif giho[i]== '-':
			result -= arr[i+1]
		elif giho[i]== '*':
			result *= arr[i+1]
		elif giho[i]== '/':
			if result >= 0:
				result//= arr[i+1]
			else:
				result = -((-result)//arr[i+1])
	if result > max:
		max = result
	if result < min:
		min = result

print(max)
print(min)

문제자체는 itertools를 사용하여 풀었기 때문에, 어렵지 않았는데 첫번째로 틀린것은

문제 조건에 의해 큰수들만 연속으로 * 가 나오면 최대 최소가 1e9, -1e9가 넘어갈 수 있었다는점 

그리고 두번째는 그냥 permutation을 쓰면 같아도 같은 순열도 중복으로 나오기 때문에

ex) list(permutation([1,1,2],3)) = [(1,1,2),(1,1,2),(1,2,1),(1,2,1),(2,1,1),(2,1,1)]

set함수를 통해 중복을 줄여주었다.

 

2차시도:

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
arr = list(map(int,input().split()))

Giho = list(map(int,input().split()))

m = int(1e11)
M = -int(1e11)

def cal(a,b,i):
	if i ==0:
		return a+b
	elif i == 1:
		return a-b
	elif i == 2:
		return a*b
	else :
		return a//b if a>=0 else -((-a)//b)

def min_max(k):
	global M
	global m
	if k > M:
		M = k
	if k < m:
		m = k
		
def bfs():
	q = deque([[arr[0],Giho,0]])
	#q에 첫번째 숫자, 기호리스트, 번호넣고 
	while q:
		result , giho, num= q.popleft()
		#만약 끝까지 다갔다면 min,max 계산
		if num == n-1:
			min_max(result)
			continue
		#끝까지 안갔다면 계산
		else:
			for i in range(4):
				if giho[i]!=0:
					t_giho = giho[:]
					t_giho[i] -=1
					q.append([cal(result,arr[num+1],i),t_giho,num+1])

bfs()
print(M,m,sep='\n')

2차시도는 permutation을 쓰지 않고, BFS를 통해서 풀었다. 똑같이 모든 경우를 보는것은 똑같지만, 끝의 계산이 다른경우 중간까지의 계산을 공유하기 때문에 시간 복잡도가 훨씬 개선 된 것을 확인할 수 있었다. 

(사실 바로 못풀고 예전 풀이를 참고했는데 좌표가 아닌 다른 형태의 문제를 bfs,dfs로 푸는 연습을 해야할 것 같다. )