14888

날짜 : 2023. 06.13 

사용 언어 : python

 

문제

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

 

 

코드

import sys


def bt(s):
    # print(s)
    if len(s) == (n-1):  # 길이 충족
        order.append(s)
        return
    for i in range(4):
        if op[operator[i]] > 0:
            op[operator[i]] -= 1
            bt(s + operator[i])
            op[operator[i]] += 1
    return


operator = ['+', '-', '*', '/']
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))  # 숫자
tmp = list(map(int, sys.stdin.readline().split()))
op = dict()  # 연산자
for i in range(4): op[operator[i]] = tmp[i]
order = list()  # 연산순서(문자열)
bt("")
# print(order)

max_val = (-1) * (int(10e9))  # 최소값 : -10억
min_val = int(10e9)   # 최대값 : 10억(10e9)

# 연산
for i in range(len(order)):
    tmp = nums[0]
    for j in range(n-1):
        if order[i][j] == "+":
            tmp += nums[j+1]
        elif order[i][j] == '-':
            tmp -= nums[j+1]
        elif order[i][j] == "*":
            tmp *= nums[j+1]
        elif order[i][j] == "/":
            tmp /= nums[j+1]
            tmp = int(tmp)
    max_val = max(max_val, tmp)
    min_val = min(min_val, tmp)

print(max_val)
print(min_val)

 

 

풀이

- 백트래킹을 활용해서 연산순서에 대한 문자열을 만들어 저장한 후 그 문자열에 대해서 값을 계산한다.

ex) nums=[1, 2, 3, 4] // '++++' => 1 + 2 + 3 + 4

 

 

알게된 점

- 결과값의 범위가 -10억부터인 것을 간과하고 max 값을 0으로 주다보니 틀렸다.

- 0을 (-1) * int(10e9)로 하니까 바로 풀림

 

 

참고 사이트

-