문제 설명

->링크<-

해결 방법

먼저 뭔가 이렇다할 방법이 보이지않았고
11팩토리얼이 최대 연산횟수(약 4000만)여서 2초면 충분히 해결 가능할 줄알고 permutaion함수를 이용한 완전탐색 코드를 짜봤다 하지만
pypy로는 통과했으나 phython으로는 타임에러가 났다ㅜㅜㅜㅜㅜ
그래서 어떤 방법이 있나 서칭을 해봤더니 DFS를 이용하는 방법도 있었다.

해답 코드

1. permutains함수를 이용한 방법

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

N = input().rstrip()
list_A = list(map(int,input().split()))
oper_num = list(map(int,input().split()))
oper_list = []
#더하기 개수만큼 더해주기
for _ in range(oper_num[0]):
  oper_list.append('+')
#빼기 개수만큼 더해주기
for _ in range(oper_num[1]):
  oper_list.append('-')
#곱하기 개수만큼 더해주기
for _ in range(oper_num[2]):
  oper_list.append('*')
#나누기 개수만큼 더해주기
for _ in range(oper_num[3]):
  oper_list.append('/')
size = len(oper_list)

max_value = -2100000000
min_value = 2100000000
#모든 경우에서 구해보고 최댓값 최솟값 추출
for operators in permutations(oper_list, size):
  tmp = list_A[0]
  #순열된 연산자 순서에따른 계산해내기
  for i in range(size):
    if operators[i] == '+':
      tmp += list_A[i+1]
    elif operators[i] == '-':
      tmp -= list_A[i+1]
    elif operators[i] == '*':
      tmp *= list_A[i+1]
    else:
      tmp = int(tmp / list_A[i+1]) 
  max_value = max(max_value, tmp)
  min_value = min(min_value, tmp)

print(max_value, min_value)

2. DFS를 이용한 방법

import sys
max_value = -2100000000
min_value = 2100000000
def DFS(depth, value, plus, minus, mul, div):
  global max_value
  global min_value
  
  if depth == N-1:
    max_value = max(max_value, value)
    min_value = min(min_value, value)
    return

  if plus > 0:
    DFS(depth+1, value + A[depth+1], plus-1, minus, mul, div)
  if minus > 0:
    DFS(depth+1, value-A[depth+1], plus, minus-1, mul, div)
  if mul > 0:
    DFS(depth+1, value * A[depth+1], plus, minus, mul-1, div)
  if div > 0:
    DFS(depth+1, int(value / A[depth+1]), plus, minus, mul, div-1)


input = sys.stdin.readline
N = int(input().rstrip())
A = list(map(int,input().split()))
plus, minus, mul, div = map(int, input().split())

DFS(0, A[0], plus, minus, mul, div)
print(max_value, min_value)

다른사람의 코드를 보고난 후

DFS를 생각도 못했고 이런식으로도 가능한지 알았다 또한 재귀 코드는 직관적으로 확 오지 않기때문에 에러가 났을 때 대처하는게 아직 능숙하지 못했다. 좀더 연습이 필요하다

걸린시간

각각 50분 30분정도 걸렸다.
첫번째 방법은 음수 나눗셈때문에 두번째 방식은 재귀문의 능숙하지 못해서 시간을 잡아먹었다 이번에 겪었으니까 분명히 다음에는 지금보다 더 쉽게 이겨 낼 수 있을 것이다.

파이썬의 음수 나눗셈 방식...

문제에서는 예를들어 -10 / 3은 -3을 취하는 것을 원했다.
따라서 파이썬 내에서

A = -10 // 3 #을 해버리면 -4가 나오게된다
A = int(-10 / 3)#이런식으로 해서 소수점을 버리는 방식을 취하면 된다!!