백준 1541 풀이 (잃어버린 괄호, 그리디)

백준에 단계별로 풀기를 가면 그리디가 DP보다 아래에 있다. 그래서 그리디가 상당히 어려운가보다 했는데.....그리디가 훨씬 쉽다. DP로 고통받았던게 슬퍼졌다.

이번 문제는 +와 -만 존재하는 식을 짰을때 괄호를 이용하여 최솟값을 찾으라는 문제였다.

40-50+30 = 20 이지만 40-(50+30) = -40 으로 만들어 보라는 소리다.

 

그럼 괄호를 어디에 쳐야하는지 생각해본다.

일단 -만나면 (를 쳐주고 다음 -를 만났을 때 )를 쳐주면 +들을 묶을 수 있다.

그렇다면 결국 중요한것은 +를 묶어주어야한다는 것이다.

따라서 처음 입력받을 때 -마다 짤라주고 안에 존재하는 것들을 합치고 빼면 된다.

 

설명하려니까 어렵다. 아래의 코드를 보면 쉽게 이해가 된다.

l = input().split('-')

for i in range(len(l)):
    if "+" in l[i]:
        tmp = sum(list(map(int,l[i].split("+"))))
        l[i] = tmp
    else:
        l[i] = int(l[i])

for i in range(1, len(l)):
    l[0] -= l[i]
print(l[0])