백준에 단계별로 풀기를 가면 그리디가 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])
'알고리즘' 카테고리의 다른 글
백준 2609 풀이 (최대공약수와 최소공배수, 유클리드 호제법) (0) | 2021.02.28 |
---|---|
백준 13305 풀이 (주유소, 그리디 알고리즘) (0) | 2021.02.28 |
백준 11399 풀이 (ATM, 그리디) (0) | 2021.02.26 |
백준 1931 풀이 (회의실 배정, 그리디) (0) | 2021.02.26 |
백준 11047 풀이 (동전 0, 그리디) (0) | 2021.02.26 |