[Baekjoon, Python] 1541번 : 잃어버린 괄호

도입

백준 단계별 풀기 그리디 알고리즘 네 번째 문제이다.

백준 1541번 문제, 입력, 출력

---

백준 1541번 입출력 예제 1

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 최솟값을 만들 수 있을 때가 언제인가! 마이너스(-)를 기준으로 식들을 나눈다. 그러면 그 식들은 양수와 플러스(+)로만 이루어져 있을 것이다. 그 식들을 다 더한 값들을 빼주면 결과적으로 최솟값이 될 것이다. 이 부분을 캐치하는 것이 이 문제의 핵심이라고 할 수 있다. "마이너스(-)를 기준으로 식들을 나눈다!"

 

2. 수가 양수라는 조건과 식의 시작과 끝은 숫자라고 했다. 이것이 의미하는 즉슨, 식의 앞에 음수가 오지 않는다라는 얘기이다.

 

3. 식의 제일 앞 숫자만 더해주고, 나머지 위에서 +로 묶여서 계산된 숫자들은 빼주면 된다.

---

코드

from sys import stdin

list_minus = stdin.readline().split('-')
num = []

for i in list_minus:
    cnt = 0
    list_add = i.split('+')
    for j in list_add:
        cnt += int(j)
    num.append(cnt)
rtn = num[0]          

for i in range(1, len(num)):
    rtn -= num[i]

print(rtn) 

---

마무리

수가 양수라는 조건과 식의 시작과 끝은 숫자라고 했다. 만약에 해당 조건이 없었다면, 제일 앞에 오는 음수의 경우에 따라 또 다른 처리를 해주어야 할 것 같다.