문제
풀이
연산자 배열 생성: 주어진 연산자의 개수에 따라 가능한 모든 연산자 조합을 생성합니다. 예를 들어, 덧셈 1개, 뺄셈 1개, 곱셈 1개가 주어지면 가능한 연산자 배열은
['+', '-', '*']등이 될 수 있습니다.순열을 사용한 모든 조합 탐색: Python의
itertools.permutations을 사용하여 이 연산자 배열의 모든 순열을 생성합니다.식 계산: 생성된 각 연산자 순서에 따라 주어진 수열에 연산자를 삽입하여 식을 만들고, 결과를 계산합니다. 계산은 문제 조건에 따라 연산자 우선순위를 무시하고 주어진 순서대로 진행합니다.
최댓값과 최솟값 찾기: 모든 가능한 식의 결과 중 최댓값과 최솟값을 찾습니다.
파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from itertools import permutations
def calc(ops):
result = A[0]
for i in range(1, N):
if ops[i-1] == '+':
result += A[i]
elif ops[i-1] == '-':
result -= A[i]
elif ops[i-1] == '*':
result *= A[i]
else:
if result < 0:
result = -(-result // A[i])
else:
result //= A[i]
return result
def solve():
operators = ['+'] * OP[0] + ['-'] * OP[1] + ['*'] * OP[2] + ['/'] * OP[3]
min_result, max_result = float('inf'), float('-inf')
for ops in set(permutations(operators, N-1)):
result = calc(ops)
min_result = min(min_result, result)
max_result = max(max_result, result)
print(max_result)
print(min_result)
if __name__ == '__main__':
N = int(input())
A = list(map(int, input().split()))
OP = list(map(int, input().split()))
solve()
팁
permutations는 Python의 itertools 모듈에 포함된 함수로, 주어진 순열 가능한 모든 요소들의 배열을 생성합니다. 즉, 입력된 요소들로 만들 수 있는 모든 순서의 조합을 반환합니다.
예를 들어, permutations([1, 2, 3], 2)를 호출하면, [1, 2, 3]로 만들 수 있는 모든 2개 요소의 순서 조합을 반환합니다. 결과는 [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]와 같을 것입니다.
이 함수는 순열을 구할 때 특히 유용하며, 복잡한 루프 구조 없이 간단히 모든 조합을 탐색할 수 있게 해줍니다. 이 문제에서는 주어진 연산자들로 가능한 모든 연산자 조합(순서가 중요함)을 찾기 위해 사용되었습니다. 예를 들어, 연산자가 ['+', '-', '*']라면, permutations 함수를 사용하여 이 연산자들로 만들 수 있는 모든 순서의 조합을 생성할 수 있습니다.
Python의 itertools 모듈에는 permutations 외에도 다양한 유용한 함수들이 많습니다. 이러한 함수들은 알고리즘 문제를 해결할 때 매우 편리하게 사용될 수 있습니다. 여기에는 순열, 조합, 카르테시안 곱 등을 쉽게 생성할 수 있는 여러 함수들이 포함되어 있습니다. 이러한 함수들을 이용하면 복잡한 반복문을 작성하지 않고도 간단하고 효율적으로 많은 문제들을 해결할 수 있습니다.
예를 들어:
itertools.combinations(iterable, r)함수는 입력된 반복 가능한 객체에서 요소의 모든 조합을 반환합니다.itertools.product(*iterables, repeat=1)함수는 여러 반복 가능한 객체들의 카르테시안 곱을 생성합니다.
이런 함수들은 특히 브루트포스 방식으로 문제를 해결할 때 유용하게 쓰일 수 있습니다.