https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱
www.acmicpc.net
문제요약:
말그대로 숫자와 연산자의 개수가 주어질 때 , (앞에서 부터 계산) 최대 최소값을 구하라
실버 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로 푸는 연습을 해야할 것 같다. )