[解答]BOJ-14888演算子の挿入

9395 ワード


📔 問題の説明

問題に答える
🧰 変数の説明

  • N
  • タイプ:整数
  • 格納データ:入力する数値を格納します.

  • operations
  • タイプ:インベントリ
  • 格納データ:使用可能な演算子を含むリスト

  • number_input
  • タイプ:インベントリ
  • 格納データ:入力数字をリスト
  • として保存する.

  • operation_input
  • タイプ:インベントリ
  • 格納データ:入力された演算子数
  • がリストされます.

  • operation_list
  • タイプ:インベントリ
  • 格納データ:
  • 非繰返しの組合せ(入力された演算子の数)を格納

  • result
  • タイプ:整数
  • 格納データ:計算値
  • を保存

  • answer
  • タイプ:インベントリ
  • 格納データ:
  • 格納計算値
    🖨解法
    1. 입력받을 변수들을 입력 받는다. [ N, number_input, operation_input ]
    2. 사용 가능한 연산자들을 저장한다. [ operations ]
    3. for문을 통해 operation_input 에 입력된 값 만큼 operations에서 꺼내서 저장한다.
    4. permutations를 통해 operations에 저장된 값 들로 사용가능한 모든 조합을 저장한다.
    5. 이때 중복된 조합이 있으면 시간이 초과되므로 set을 통해 중복을 제거해준다.
    6. 이중 for문을 통해 연산자를 뺀 후 그 연산자에 값들을 계산한다.
    7. answer에 저장된 값들을 max와 min을 통해 최대, 최소 값을 출력해준다.
    
    from itertools import permutations
    import sys
    N = int(sys.stdin.readline())
    operations = ['+', '-', '*', '/']
    number_input = list(map(int, sys.stdin.readline().split()))
    operations_input = list(map(int, sys.stdin.readline().split()))  # + - * / 순서대로 숫자를 입력
    
    operation_list = []
    
    for i in range(4):
        for j in range(operations_input[i]):
            operation_list.append(operations[i])
    print(operation_list)
    operation_list = list(set(permutations(operation_list)))
    # 가능한 조합을 모두 사용하기 위해 permutations를 사용하여 조합들을 list에 저장
    # 이때 set을 사용하지 않고 중복된 조합들도 사용하게 할 시 시간초과가 뜨므로 set을 통해 중복은 제거해준다.
    answer = []
    
    for i in operation_list:
        result = number_input[0]
        for j in range(N - 1):
            if i[j] == '+':
                result += number_input[j + 1]
            elif i[j] == '-':
                result -= number_input[j + 1]
            elif i[j] == '*':
                result *= number_input[j + 1]
            else:
                if result // number_input[j + 1] < 0:
                    result = -(-result // number_input[j + 1])
                else:
                    result = result // number_input[j + 1]
    
        answer.append(result)
    print(max(answer))
    print(min(answer))
    
    時間:608ミリ秒