[그리디 알고리즘] ★ 1541번 - 잃어버린 괄호(완전탐색)

[백준] 1541번 - 잃어버린 괄호

1) 문제 해결 아이디어

- 기준으로 괄호를 쳤을 때 최솟값이 된다.

 

60+20-50+10-20+30 이 입력으로 들어오면

(60+20)-(50+10)-(20+30) 이렇게 괄호를 쳤을 때 최소값이 된다.

상식적으로 최소값을 만들기 위해서는 큰 값으로 뺴주어야 하는데

- 기준으로 나누었기 때문에 괄호 ( ) 안에는 항상 숫자 혹은 더하기로만 이루어진 식이 오게 된다.

 

1. - 기준으로 분리한 결과

["60+20", "50+10", "20+30"]

 

2. 각각을 + 기준으로 분리하고 int형 변환한 결과

[60, 20], [50, 10], [20, 30]

 

3. 첫번째 결과에서 나머지 결과들을 모두 뺀 결과

80 - 60 - 50 = -30

 

첫번째 괄호의 계산값에서 나머지 괄호들의 계산값을 모두 뺀 값이 정답이다.

 

2) 소스코드

s = input().split("-")  # - 기준 분리
res = 0    # 최솟값

# 첫번째 괄호의 합 - (나머지 괄호의 합)
n = list(map(int, s[0].split("+")))
res += sum(n)  # 첫번째 괄호의 합

for i in s[1:]:
  n = list(map(int, i.split("+")))
  res -= sum(n)  # 나머지 괄호들의 합 빼기

print(res)

 

[참고] https://pacific-ocean.tistory.com/228

[백준] 1541번(python 파이썬)