[백준] 1541 잃어버린 괄호

iamjinseo·2022년 8월 4일

그리디 백준

문제풀이-Python

목록 보기

32/134

문제

입출력

해설

들어가기 전에

-가 나오면 괄호를 치고 또 다른 -가 나오면 괄호를 닫아야 한다.
예시 :

50 - 20 + 30 이 있을 떄 50 - (20 + 30)이 최적의 해다.
50-20-30이 있을 때 50-(20)-(30)이 최적의 해다.
만약에 50-(20-30)과 같이 괄호를 친다면? 60이라는 답이 나온다(땡)

그러니까 이런 형태가 나와야 한다는 뜻이다. +연산으로 최대한 수를 늘린 다음에 -를 입혀 한꺼번에 확 빼는 식으로...

해설

120 - 70 + 50 + 10 - 60
라는 식이 있을 때

인풋으로 받은 식을 - 기준으로 나눈다.
마이너스로 나눈 식 = input().split('-')

그리고 맨 처음부터 -가 나오기 전까지의 식을 모두 더한다. (이전까지는 모두 +로만 이루어진 식이므로)

for 플러스로 나눈 숫자 in 마이너스로 나눈 식[0].split('+'):
    합계 += int(플러스로 나눈 숫자

그리고 그 다음 식부터는 +를 기준으로 숫자를 분리한 다음 모두 sum에서 빼버린다.

for 플러스로 나눌 식 in 마이너스로 나눈 식[1:]:
    for 플러스로 나눈 숫자 in 플러스로 나눌 식.split('+'):
        합계 -= int(플러스로 나눈 숫자)

코드

import sys
arr = sys.stdin.readline().split('-') #-로 쪼개기
sum = 0
for num in arr[0].split('+'):
    sum += int(num)

for num in arr[1:]:
    for i in num.split('+'):
        sum -= int(i)
print(sum)

시도

이런 저런 식들을 세워가며 어떻게 해야 최소값을 충족시킬까 하다

이렇게 생각해냈다.

-를 만나면 뒤에 괄호를 치고 또 -를 만나면 앞에 괄호를 닫는 것이다.

그래서 스택을 쓸까 했는데 문자열로도 할 수 있을 것 같아 도전해보았다.

import sys
instr = sys.stdin.readline()
 
start = 0 #괄호 시작위치
for i in range(start, len(instr)):
    if instr[i] == '-':
        # a - b => a - ( b
        instr = instr[:i+1] + '('+instr[i+1:]
        print(instr)
        start = i+1
        print(start)