[백준 2024/09/19] 14888번 연산자 끼워넣기

1. 문제

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

 

2. 접근 방법

어떻게 연산자들의 경우의 수를 표현할 수 있을까 고민해 보았다.

처음에 잘 생각이 나지 않았지만, 섣불리 접근하다간 오히려 시간을 많이 쓸 것 같아서 더 고민해 보았다. - 요런 태도가 코테에서는 중요한 것 같다. (메모메모~)

예를 들어 

+ : 2개

- : 1개

* : 1개

/ : 1개

라면, 

+가 중복 되기에, 중복 case를 제외시켜 주어야 한다.

 

따라서, dfs를 이용해서

dfs(현재 연산 경우의 리스트, 사용하고 남은 연산자 리스트) 로 문제 풀이를 시작한다.

만약, 현재 연산자 경우의 리스트의 len이 연산자 개수라면, 해당 리스트를 total 에 append하고 return 한다.

 

그 외는 for i in range(4)를 하면서, 특정 연산자가 남았다면, cur_list에 append 하고, 사용한 연산자를 뺀 리스트를 다시 넣어준다.

 

ex)

만약 연산자를 [2, 1, 1, 1]로 넘겨주었고, +를 사용하였다면 다음 dfs로는 ([1], [1, 1, 1, 1]) 을 넘겨주면 된다.

 

이렇게 만든 연산자 경우의 수를 가지고, 계산을 진행하면 된다. -> 여기서 시간 초과가 나지 않을까 걱정을 했지만 다행히 나지 않았다.

만약 시간 초과가 났다면, memoization 사용 여부를 고려했을 것 같다.

 

3. 코드

def dfs(cur, left):
    if len(cur) == num_cnt - 1:
        total.append(cur)
        return

    for i in range(4):
        if left[i] > 0:
            left[i] -= 1
            dfs(cur+[i], left)
            left[i] += 1


def op_calculate(nums, total):
    values = []
    base_num = nums.pop(0)
    for t in total:
        value = base_num

        for i in range(num_cnt - 1):
            if t[i] == 0:
                value += nums[i]
                continue
            elif t[i] == 1:
                value -= nums[i]
                continue
            elif t[i] == 2:
                value *= nums[i]
                continue
            else:
                if value < 0:
                    value *= -1
                    value = value // nums[i]
                    value *= -1
                    continue
                value = value // nums[i]
        values.append(value)

    return min(values), max(values)


if __name__ == "__main__":
    num_cnt = int(input())
    nums = list(map(int, input().split()))
    op = list(map(int, input().split()))
    total = []
    dfs([], op)
    min_v, max_v = op_calculate(nums, total)
    print(max_v)
    print(min_v)