[정글 알고리즘] - [하] 백준1541- 잃어버린 괄호- 실버2

백준 · 그리디 · 문자열 파싱 · 실버2

수식에서 괄호를 적절히 쳐서 결과를 최소로 만드는 대표 그리디 문제

문제 링크 바로가기

문제 한눈에 보기

목표	괄호를 적절히 넣어 식의 값을 최소로 만들기
핵심 전략	첫 번째 '-' 뒤의 모든 수를 한꺼번에 빼기
풀이 방식	문자열 분리 + 그리디

핵심 1

값을 최소로 만들려면 한 번 빼기 시작한 뒤에는 최대한 많이 빼야 한다.

핵심 2

그래서 첫 '-' 기준으로 문자열을 나누면 된다.

핵심 3

맨 앞 부분은 더하고, 그 뒤 부분들은 각각 합쳐서 전부 뺀다.

최종 코드

s = input()
part = s.split("-")

result = sum(map(int, part[0].split("+")))

for p in part[1:]:
    result -= sum(map(int, p.split("+")))

print(result)

풀이 흐름

1. 식을 - 기준으로 나눈다.
2. 맨 앞 덩어리는 그대로 더한다.
3. 그 뒤 덩어리들은 내부의 + 들을 모두 더한 뒤 한꺼번에 뺀다.

예시 이해

55-50+40

첫 번째 '-' 뒤를 전부 괄호로 묶으면 55 - (50 + 40) 이 되어 결과는 -35 가 된다. 이것이 최소값이다.

왜 그리디인가?

한 번 '-'를 만난 순간부터 이후 수들을 최대한 크게 묶어서 빼는 것이 항상 이득이다. 이 선택이 전체 최적해로 이어지므로 그리디가 성립한다.

한 문장 정리

잃어버린 괄호는 첫 번째 '-' 뒤의 수들을 전부 묶어 빼면 최소값이 된다는 아이디어만 잡으면 끝나는 그리디 문제다.