파이썬 / BOJ 백준 / 1541 잃어버린 괄호 - 그리디 알고리즘

파이썬 / BOJ 백준 / 1541 잃어버린 괄호 - 그리디 알고리즘

 

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

1541번: 잃어버린 괄호

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

 

풀이

1. 그리디 알고리즘을 사용하여 풀 수 있는 문제입니다.

2. 최솟값을 만들기 위해서는 - 기준으로 괄호를 쳐주면 됩니다.

3. 입력을 받을 때 - 기준으로 입력을 받아줍니다.

4. 리스트의 맨 처음의 원소들은 더해주고, 나머지 리스트의 원소들  빼줍니다.

전체 코드

arr = input().split('-')
sum = 0

for i in arr[0].split('+'):
    sum += int(i)
for i in arr[1:]:
    for j in i.split('+'):
        sum -= int(j)
#print(arr)
print(sum)