백준 / 연산자 끼워넣기 / 14888

Question

문제링크
Silver 1

자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

2
5 6
0 0 1 0

Output

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

30
30

Logic

기본 구조 : permutations

1. 입력받은 연산자 갯수를 바탕으로 모든 연산자 조합 경우의 수를 생성한다.
2. 각 경우의 수에 따라 순차적으로 계산하고, 최대값과 최소값을 최신화한다.

• 이 때 기본 연산 규칙을 따르지 않고 순서대로 하므로, 한번에 계산하지 않고 한 연산씩 끊어서 해야 한다.
• 또한 나눗셈 연산의 경우 음수의 계산이 다르므로, 조건을 만족하기 위해서 나눗셈 계산 결과를 int 함수를 취하면 된다.

순열로 문제를 풀 경우에 python으로 제출하면 시간초과가 걸렸으나, PyPy3으로 제출하니 성공하였다.

python으로 풀 경우에는 dfs방식으로 풀어야 할 것 같다.

Code

from sys import stdin
from itertools import permutations

N = int(stdin.readline().strip())
data = list(map(int,stdin.readline().strip().split()))
a,b,c,d = map(int,stdin.readline().strip().split())
operands = ['+']*a + ['-']*b + ['*']*c + ['/']*d

minn = 1000000001
maxx = -1000000001

for oo in list(permutations(operands,N-1)):
    res = data[0]
    for op,nn in zip(oo,data[1:]):
        if op == '+':
            res += nn
        elif op == '-':
            res -= nn
        elif op == '*':
            res *= nn
        else :
            res = int(res/nn)
    
    minn = min(res,minn)
    maxx = max(res,maxx)

print(maxx)
print(minn)