[수학/그리디] 백준 1541 잃어버린 괄호 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1541번: 잃어버린 괄호

 

 

 

2. 문제 풀이

 -와 +로 이루어진 식에 임의로 결합법칙을 적용해 최소값을 만드는 문제입니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 어렵게 생각하면 어렵고, 쉽게 생각하면 쉬운 문제입니다. 일단, 최소값이 나오기 위해서는 음수가 최대한 많이 나와야 합니다. 따라서 최대한 길게 음수식을 만들어 줍니다.

 여기서 음수식은 - (a + b + ... + z) 인 형태를 뜻합니다.

 

3+2-2+3+2+1-0+2+3-2-1+2

 위와 같은 식을 변환하면 아래와 같습니다.

 

3+2-(2+3+2+1)-(0+2+3)-(2)-(1+2) = 5 - 8 - 5 - 2 -3 = -13

 

 

 

3. 코드

import sys
input = sys.stdin.readline

term = list(input().rstrip())
res = 0
num = ''
minus = False

# minus가 1번만 나와도, 그 다음부터는 음수
for i in term:
    # minus가 한 번도 안 나왔을 때
    if not minus:
        if i == '-':
            minus = True
            res += int(num)
            num = ''
        elif i == '+':
            res += int(num)
            num = ''
        else:
            num += i

 위 음수식을 잘 이해하면, -(음수 부호)가 1번만 나오면 그 뒤는 모두 음수가 됨을 알 수 있습니다.

 -가 한 번도 나오지 않았을 때에는 +로 숫자를 더해줍니다.

 

 

    # minus가 한 번 이상 나왔을 경우
    elif minus:
        if i == '-' or i == '+':
            res -= int(num)
            num = ''
        else:
            num += i

 -가 한 번이라도 나온 뒤에는, 숫자를 빼줍니다.

 

 

if minus:
    res -= int(num)
else:
    res += int(num)
print(res)

 위 반복문에서는 - 혹은 +부호가 나와야 num을 연산했습니다. 맨 끝의 숫자는 -, +가 뒤에 붙지 않으므로 따로 더하거나 빼줍니다.

 

 

<전체 코드>

import sys
input = sys.stdin.readline

term = list(input().rstrip())
res = 0
num = ''
minus = False

# minus가 1번만 나와도, 그 다음부터는 음수
for i in term:
    # minus가 한 번도 안 나왔을 때
    if not minus:
        if i == '-':
            minus = True
            res += int(num)
            num = ''
        elif i == '+':
            res += int(num)
            num = ''
        else:
            num += i

    # minus가 한 번 이상 나왔을 경우
    elif minus:
        if i == '-' or i == '+':
            res -= int(num)
            num = ''
        else:
            num += i

if minus:
    res -= int(num)
else:
    res += int(num)
print(res)