[ 백준 ] 1541번 : 잃어버린 괄호 (파이썬)

문제 )

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

1541번: 잃어버린 괄호

 

[ 풀이 ]

우선 식의 값에 괄호를 넣어 최솟값이 되도록 하려면 '-'를 기점으로 나눠서 괄호를 씌워야 한다

문제에서 나온 예제를 보면  55-50+40 의 식의 값을 최소로 만들기 위해 '-'를 기점으로 괄호를 씌운다 
즉, 55-(50+40) 으로 만들어줘야 -35로 식의 값을 최소로 만들 수 있다.

우선 '-'를 기점으로 문장을 나눠서 list S에 저장해야한다. 

 

 

< calculate 함수의 Algorithm >

✔ '-'를 기점으로 분리된 값이 존재하는 → s
✔  식에 괄호를 씌워 만들 수 있는 최솟값 → result
✔ s의 하나의 value만을 계산한 값 → one

1. s의 제일 첫번째에 있는 value(식일 수도 있고 숫자만 있을 수도 있음)의 값을 구해준다  
        (1) s[0]을 '+'를 기준으로 분해한 값에 1개씩 접근한다 → i
        (2) 그 값들을 result에다가 더해준다
2. s의 두번째부터 끝까지 value들에 1개씩 접근한다 → i
        (1) one값을 초기화해준다
        (2) 원소 i의 계산한 값을 구해준다
                    Ⅰ.  i를 '+'를 기준으로 분해한 값에 1개씩 접근한다 → j
                    Ⅱ. 그 값들을 더해 one값을 구해준다
        (3) reslut에다가 one 값을 빼준다 

 

- python code

import sys
input=sys.stdin.readline


def calculate(s):
    result=0 # 최솟값
    #제일 첫번째에 있는 value의 값 구하기
    for i in s[0].split('+'): # '+'를 기준으로 분해
        result+=int(i)
    # 두번째부터 끝까지 value들에 접근
    for i in s[1:]:
        one=0   # 하나의 value만 계산 
        for j in i.split('+'): #'+'를 기준으로 분해
            one+=int(j)
        result-=one
    return result


S=input().split('-') # '-'를 기준으로 list에 저장 
print(calculate(S))