[C++/BOJ] 백준 1541 잃어버린 괄호 (그리디)

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

1541번: 잃어버린 괄호

왜 파이썬 파이썬 그러는지 알겠다. 파이썬 최고!!

 

 

 

📄 문제

 

+ , -, 숫자 , 괄호로 이루어진 식에서 괄호를 지우고 

이 식의 값을 최소로 만들도록 다시 넣었다. 

괄호를 적절히 최소로 만드는 프로그램을 작성하라

 

 

🖌어떤 생각 ?

 

이 문제를 처음 보고 "뭐야 어떻게 괄호 만으로 값을 바꾸라는 말이지?

덧셈, 뺄셈은 괄호에 상관없이 결과가 똑같잖아?"

라는 생각이 들어 코드를 찾아보았다. 너무 고정관념에 갖혀있었다. 

 

32 - 55 + 40 이 있을때

나는 (32 - 55 ) + 40 이거나 32 + (- 55 + 40 ) 을 생각했다. 

이러면 17이 나온다. 

하지만 32 - ( 55 + 40 ) 이렇게 하면 -63이 된다 !

 

- 기호와 숫자사이에 괄호를 넣을 생각을 못했다!

이 방법이면 한번 '-'가 나오면 뒤에 모든 숫자는 뺄셈 할수있다.

 

 

 

🔑 그래서 어떻게 푸는데?

 

1) '-'를 기준으로 나눈다. 

 

2) '-'를 기준으로 나눠지기 전 => '+'만 가능

값을 모두 더해준다.  ('+'를 기준으로 split하여)

 

3) '-' 를 기준으로 나눠지고난 후 => '-' 가능

값을 빼준다. ('+'를 기준으로 split하여)

 

 

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(sum)

 

아이 짧다 아이 좋아

 

 

 

<참고 코드>

https://sungmin-joo.tistory.com/67

[백준] 1541번 잃어버린 괄호 Python 해설 (그리디 알고리즘)