[python] BOJ 1541 잃어버린 괄호

백준 1541번 잃어버린 괄호

그리디 알고리즘 문제이다.

예제를 보면 알 수 있듯이, 식이 주어지면 적절하게 괄호를 추가해서 가장 작은 값을 만들어야한다.

1번 예시의 경우에는 55-(50+40) = -35 를 만든 경우이다. 몇가지 예시를 더 생각해보자

 

예시1) 1 + 2 + 3 + 4 + 5 + 6 + 7 - 9 위의 경우엔 어떻게 괄호를 쳐도, 괄호를 치지않은 경우와 답이 같다. 그 이유는 식의 마지막에 - 부호가 있기때문 예시2) 1 + 2 + 3 + 4 + 5 - 6 + 7 + 9 위의 경우는 6 부터 9까지 괄호를 치면 된다.  1 + 2 + 3 + 4 + 5 - (6 + 7 + 9) 예시3) 1 + 2 + 3 + 4 + 5 - 6 + 7 - 9 위의 경우는 6부터 7까지를 괄호 치면 된다. 1 + 2 + 3 + 4 + 5 - (6 + 7) - 9

위의 예시들을 통해 최솟값을 만드는 방법을 유추할 수 있다.

식에서 마이너스 부호를 발견했을때, 그 뒤에 등장하는 모든 숫자들의 합을 앞의 숫자들에서 빼면 된다.

즉 처음 마이너스 부호를 발견한 순간이 중요한 조건이 되는 것이다. 한번 소스코드를 작성해보자.

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

exp = input()   #처음 마이너스 부호가 등장하는 인덱스 찾기 #초기값 0으로 설정 minus_idx = 0   for i in range(0, len(exp)):     if exp[i] == '-':         minus_idx = i         break   #마이너스 부호가 등장하는 앞까지 숫자의 합 계산 sum1, sum2 = 0, 0 number = 0 for i in range(0, minus_idx + 1):     if exp[i] >= '0' and exp[i] <= '9':         number = number * 10 + int(exp[i])     else:         sum1 = sum1 + number         number = 0 #마이너스 부호의 뒷부분 숫자의 합 계산 for i in range(minus_idx + 1, len(exp)):     if exp[i] >= '0' and exp[i] <= '9':         number = number * 10 + int(exp[i])     else:         sum2 = sum2 + number         number = 0 sum2 = sum2 + number   if sum1 == 0:     result = sum2 else:     result = sum1 - sum2   print(result)   Colored by Color Scripter

cs

내가 생각한 알고리즘으로 해결할 수 있었다.