[백준] 연산자 끼워넣기 (2)

https://www.acmicpc.net/problem/15658

15658번: 연산자 끼워넣기 (2)

1. 문제 이해

N개의 수로 이루어진 수열의 숫자 사이사이에 연산자를 끼워넣어서 최소, 최대값을 구하는 문제

2. 문제 접근

N이 최대 11까지 가능하고 연산자의 개수는 40까지 가능하므로 대략 40P4라고 생각해보아도 시간초과가 나지 않기 때문에 조합을 활용하여 풀이

3. 풀이

import sys
MAX = 1000000001
sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n = int(input())

nums = list(map(int, input().split()))
op = list(map(int, input().split()))

max_ans = -MAX
min_ans = MAX

def cal(operation, val, nextNum):
    if operation == 0:
        return val + nextNum
    elif operation == 1:
        return val - nextNum
    elif operation == 2:
        return val * nextNum
    else:
        return int(val/nextNum)

def permutations(depth, val):
    global max_ans, min_ans

    if depth >= n - 1:
        max_ans = max(max_ans, val)
        min_ans = min(min_ans, val)

        return


    for i in range(4):
        if op[i] == 0:
            continue

        op[i] -= 1
        ret = cal(i, val, nums[depth + 1])
        permutations(depth + 1, ret)
        op[i] += 1

permutations(0, nums[0])

print(max_ans)
print(min_ans)

4. 회고

문제의 난이도 자체는 높지 않았지만 파이썬의 나눗셈에 대해서 다시 학습하게 되었습니다. 이 문제의 핵심은 음수의 나눗셈 처리인데 C++14를 기준으로 하기에 음수를 양수로 바꾼 뒤 몫을 취하고 몫을 음수로 변경해야합니다. 단순하게 a // b를 이용하여 처리하게 되면 내림처리하기 때문에 -1 // 2 를 하게 되면 -0.5 -> -1이 되게 됩니다. 하지만 C++14를 기준으로 하면 -1 / 2 -> -(1 / 2) -> -0 -> 0이 되어야합니다. 그렇기 때문에 나눗셈을 처리할 때 int(a / b)를 통하여 소수점을 버리는 처리를 해주어야합니다.