[백준 알고리즘] 1541번 : 잃어버린 괄호 (Python) 문제 풀이

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

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

 

1541번: 잃어버린 괄호

 

문제 풀이 : 

이 문제는 그리디 알고리즘 그리고 수학, 문자열 파싱이 들어간 문제이다.

많은 개념들이 들어가있다보니 어려워보이지만 생각보다 풀이는 간단했다.

그리디 즉, 욕심 최적해 값은 "식의 결과값이 최소가 되는 것이다." 

그렇다면 우선 어떻게해야 최소 값이 나올까?

 

예를 들어보자

문제에서 나온 예제 55-50+40 에서 최소값이 나오려면 55-(50+40) 이런식으로 괄호를 쳐야한다.

즉, - 기호 뒤에 식에 괄호를 치는 것이 최소값이 나오는 가장 효율적인 방법이다.

그렇다면 60+50-40은 어떤식으로 괄호를 쳐야할까?

60+50-(40) 이런 식으로 괄호를 쳐야지만 최소값이 나온다. 

 

수학적인 개념이 조금 들어가지만, 최소값으로 나오게 하려는 생각방식

즉, 최적해를 구하려고 생각하는 것이 그리디알고리즘의 핵심이다.

 

A = input().split('-')
Sum = 0
 
for i in A[0].split('+') :
    Sum += int(i)
        
for i in A[1:] :
    for j in i.split('+'):
        Sum -= int(j)
 
print(Sum)

GitHub - ois0886/BJ_Python