잃어버린 괄호

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

백준에 단계별로 풀기를 가면 그리디가 DP보다 아래에 있다. 그래서 그리디가 상당히 어려운가보다 했는데.....그리디가 훨씬 쉽다. DP로 고통받았던게 슬퍼졌다. 이번 문제는 +와 -만 존재하는 식을 짰을때 괄호를 이용하여 최솟값을 찾으라는 문제였다. 40-50+30 = 20 이지만 40-(50+30) = -40 으로 만들어 보라는 소리다. 그럼 괄호를 어디에 쳐야하는지 생각해본다. 일단 -만나면 (를 쳐주고 다음 -를 만났을 때 )를 쳐주면 +들을 묶을 수 있다. 그렇다면 결국 중요한것은 +를 묶어주어야한다는 것이다. 따라서 처음 입력받을 때 -마다 짤라주고 안에 존재하는 것들을 합치고 빼면 된다. 설명하려니까 어렵다. 아래의 코드를 보면 쉽게 이해가 된다. l = input().split('-') f..