[백준/파이썬] 1541번 잃어버린 괄호 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1541번 잃어버린 괄호
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

+와 -로 이루어진 수식을 괄호를 적절히 쳐서 결과값을 최소로 만들어야 합니다.

핵심 관찰은 다음과 같습니다.

• 첫 -가 나온 뒤의 수들은 전부 묶어서 한 번에 빼는 것이 항상 최소

• 즉, 첫 - 이후의 +는 모두 -처럼 처리하면 됩니다.

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

q = input()
q = q[:q.find('-')] + q[q.find('-'):].replace('+', '-')
l = q.split('-')
l[0] = l[0].split('+')
tmp = 0
for i in range(len(l[0])):
    tmp += int(l[0][i])
l[0] = tmp
for i in range(1, len(l)):
    l[0] -= int(l[i])
print(l[0])

설명

코드는 아래 순서로 처리합니다.

• 첫 - 이후 구간에서 +를 모두 -로 바꿉니다.
• - 기준으로 분할한 뒤, 첫 묶음은 + 합을 계산합니다.
• 나머지 묶음은 모두 첫 값에서 빼면 최솟값이 됩니다.

수식 전체를 괄호 탐색으로 완전 탐색하지 않고,
그리디한 규칙 하나로 O(N)에 해결할 수 있습니다.

---

• 백준 문제풀이 전체 목록 보기

---