[백준] 1541번 잃어버린 괄호

 

[아이디어]

어디에 괄호를 쳐야 값이 최소가 될까?

결론 : - 를 최대한 많이 만들 수 있는곳, -를 최대한 많이 만들면 최소가 된다.

 

# 예시 1

55-50+40-30

 

먼저 - 기준으로 식을 분리시키면   (최종연산에서 -해줄 것이므로 일단 나눠놓고 시작)

>> 55, 50+40, 30

 

이때, 최소가 되는 값은 55-(50+40)-30 이다.

 

왜?

그래야 - 개수가 제일 많아지니까.

+도 -로 바꿀수있다면 최소가 되는것. 즉, +를 포함한 요소에 괄호를 쳐주면 됨.

 

[Wrong] - 런타임에러(valueError)

import sys
input = sys.stdin.readline
string=input().rstrip()
res=0

li=string.split('-') #-기준으로 자른다
numList=[int(li[0])] #첫번째원소는 정수로 변환후 numList에 추가
for l in li[1:]: #첫번째원소는 제외하고 시작
    if '+' in l:
        tmp_li=l.split('+')
        tmp_li=list(map(int,tmp_li))
        num_sum=sum(tmp_li)
        #print(num_sum)
        numList.append(num_sum*(-1))
        #합을 계산해서 -해주고 numList에 넣음
    else:
        #print(l)
        numList.append(int(l)*(-1))   #단일숫자면 숫자로바꿔 numList에 넣음
res=sum(numList)

print(res)

 

[반례] 

[입력]

10+20+30+40

[출력]

입력값에 "-"가 없는 경우 li[0]는 문자열이기 때문에 int로 변환할 수 없음..

[해결]

import sys
input = sys.stdin.readline

string=input().split('-')  #-기준으로 string을 분리
numList=[]                 #정수값만 추출한 리스트 numList
res=0                      #계산한 최소값 res

for s in string:
    sum=0
    tmp=s.split('+')      # +가 있으면 분리시킴
    for t in tmp:          
        sum+=int(t)       #이제 연산자 없이 모두 숫자만 남음. 정수로 변환후 계산.
    numList.append(sum)   #계산해준 sum을 numList에 추가
res=numList[0]            #첫번째 항은 -해주면 안됨. 따로 res에 추가.
for n in numList[1:]:     #두번째 항부터 -를 최종 계산
    res-=n
print(res)