Greedy_11_잃어버린 괄호(1541)
Greedy11잃어버린 괄호(1541)
문제
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
풀이
경우를 생각해 보자.
세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.
그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.
괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
첫째 줄에 정답을 출력한다.
경우를 생각해 보자.
1-2+3+4+5+6-7
1+2+3+4+5+6-7
1+2+3+4+5+6-7+8
1+2+3+4+5+6-7-8
'-' 가 나타났을 때의 경우를 보면
'-' 뒤의 '+'가 있다면 계속 걔네 끼리는 더해서 몸을 부풀리는게 좋다, 즉 괄호로 묶어주어 크게 한번에 빼는 것이 좋다.
'-' 뒤의 '-' 가 있다면 괄호 없이 빼서 더 작은 수를 만든다.
풀이 !!!
- '-' 기준으로 나누어 원소 저장 5-5+4 라면 '5' '5+4' 로 저장
- '-' 기준으로 나뉘어진 원소에 접근
- '+' 기준으로 나누어 배열에 append
- 첫번째 append 된 원소 기준으로 이후 원소들을 다 빼줌
코드
import sys
sys.stdin = open("input.txt","rt")
def input():
return sys.stdin.readline().rstrip()
subNum = input().split('-') # '+' 기준으로 나누어 원소 저장 5-5+4 라면 '5' '5+4' 로 저장
cal = []
for i in subNum:
val = 0
plusNum=i.split('+')
for j in plusNum:
val+=int(j)
cal.append(val)
stdNum = cal[0]
for j in range(1,len(cal)):
stdNum -= cal[j]
print(stdNum)
배운 것
subNum = input().split('-')
'-'를 기준으로 앞 뒤 원소 저장for i in subNum: plusNum=i.split('+')
subNum이라는 string 원소에 하나하씩 접근하면서 '+'를 기준으로 plusNum이라는 string에 원소 저장
코멘트
split의 쓰임새를 더 알았네
Author And Source
이 문제에 관하여(Greedy_11_잃어버린 괄호(1541)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Greedy11잃어버린-괄호1541저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)