[BOJ] 14888. 연산자 끼워넣기

문제

연산자 끼워넣기 (https://www.acmicpc.net/problem/14888)

풀이

1. 초기접근

• 문제조건 해석
  • N <= 11 로, 매우작음.
  • 모든 경우의 수를 다 해본다고 할 경우, 시간 복잡도 O(10!) 으로 1초 안으로 출력을 뽑아낼 수 있음.
  • 연산자를 나열할 때, 순서에 따라 결과 값이 달라지므로, '순열' 을 사용해야 함.
• 알고리즘
  • 입력받은 연산자로 만들 수 있는 모든 순열을 탐색해보며, 최대값과 최소값을 찾음.
  • 순열을 만드는 방법은 파이썬 내장 함수인, itertools.permutations() 로 손쉽게 구현
• 코드

n = int(input())
a = list(map(int, input().split()))
op_cnt = list(map(int, input().split()))
op = []
for idx, value in enumerate(op_cnt):
    op.extend([idx]*value)

import itertools

max_value = float('-inf')
min_value = float('inf')
for ops in itertools.permutations(op):
    res = a[0]
    for operator, operand in zip(ops, a[1:]):
        if operator == 0:
            res += operand
        elif operator == 1:
            res -= operand
        elif operator == 2:
            res *= operand
        else:
            res = int(res / operand)
    max_value = res if res > max_value else max_value
    min_value = res if res < min_value else min_value
print(max_value)
print(min_value)

2. 유의할 점

• python으로 제출할 시, 시간초과가 뜸.
• pypy 로 제출하면 정답.