백준 1541번 잃어버린 괄호 문제 - 그리디 알고리즘

1541번: 잃어버린 괄호

백준 1541번

 

괄호를 집어넣어서 계산 결과값이 최소가 되도록 하는 문제로, 가장 최소가 되도록 만들어야 한다.

생각해보면 - 가 최소가 되게 하니, - 가 나온 다음부터 그 다음 - 까지 쭉 더한 수를 한번에 빼준다면 최솟값이 나올 수 있다는 것을 예상할 수 있다.

최소가 나와야하니 - 가 중심이 되어야함을 중점으로 두고 문제를 풀면 문제풀이 방향을 정할 수 있을 것 같다.

코드

arr = input().split('-')
answer = 0
#arr[0]는 더하는 부분
for i in arr[0].split('+'):
    answer += int(i)
#arr[1]부터는 다음 - 가 나올 때 까지 더해서 한 번에 빼준다
for k in arr[1:]:
    for j in k.split('+'):
        answer -= int(j)
print(answer)

조심해야하는 부분은 arr[0]은 예제 1로 치면 '55' 인데

이 부분은 항상 더하는 부분이기 때문에 만약 arr[0]이 '55+20+30' 와 같다면 '+'을 중심으로 split로 처리해야함을 놓치지 말아야한다.

대충 안다고 머릿속으로 계산하다가 실수가 나오기 쉽다! 연습장에다가 직접 손으로 써보면서 푸는게 좋은 것 같다.

 

출처: https://sungmin-joo.tistory.com/67 [Big-Joo의 공부기록:티스토리]