백준 / 1541 / 잃어버린 괄호

문제

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

숫자와 +, - 로 구성된 수식이 있다고 했을 때, 적당히 괄호를 쳐서 수식의 계산 값이 최소가 되도록 괄호의 위치를 결정하는 문제
실제로 괄호의 위치를 구할 필요는 없고, 괄호가 있다고 했을 때 계산값이 최소가 되기만 하면 된다.

접근방식

직관적으로 +,-로만 구성되어있다고 하면 연속된 +항을 모두 괄호로 묶어서 먼저 계산을 한다.

그다음 -만 남을텐데, -는 무조건 왼쪽에서 오른쪽으로 순서대로 빼주는 것이 최소가 된다.

 

생각해보면, 최소가 되려면 - 뒤에 있는 값은 무조건 커야 큰 수를 뺄 수 있다.

그리고 수식에 -로만 구성이 되어있다고 하면 일부러 괄호를 쳐서 작은 값을 만들어서 뺄 필요는 없다.

 

예)

2-2-2 = -2 지만

2-(2-2) = 2 - 0 = 2 가 된다.

괄호를 쳐서 굳이 작은 숫자를 만들어서 뺄 필요가 없다.

(풀이)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re

line = sys.stdin.readline().strip()

oper = []
for ch in line:
    if ch == '+' or ch == '-':
        oper.append(ch)
digits = [int(x) for x in re.split('\+|-', line)]
while True:
    try:
        op_idx = oper.index('+')
        oper.pop(op_idx)
        digits[op_idx] += digits[op_idx+1]
        digits.pop(op_idx+1)
    except:
        break
answer = digits[0]
for idx in range(1, len(digits)):
    answer -= digits[idx]

print(answer)

 

회고

직관적으로 접근했는데 한번에 성공했다.

때로는 복잡하게 생각하지 않는 게 도움이 되기도 한다는 것을 느꼈다.