아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

마법천자문

시간 제한1초메모리 제한1024 MB

요약
‘+’와 ‘-’로 이루어진 문자열을 번갈아 나오는 수(“+-”는 11, “+”는 10, “-”는 1)와 연산자로 나누고, 계산 결과가 최대가 되는 해석을 찾는다.
난이도

보통10점 중 7점

유형
동적 계획법, 그리디, 문자열
정답자
아직 제출이 없습니다

문제

최근 만화 마법천자문을 감명 깊게 읽은 연두는 모든 수를 한자로 적기 시작했다. 그런데 수업을 들으면서 필기해 놓은 내용을 복습하던 도중, 도저히 알아볼 수 없는 식을 발견했다.

+----+-+-

알고 보니 이 식은 숫자 1010을 나타내는 "열 십 (十)"과 더하기를 나타내는 ++, 숫자 11을 나타내는 "한 일 (一)"과 빼기를 나타내는 −-가 뒤섞여 있어 알아볼 수 없던 것이었다. 이 식은 수많은 해석이 가능해서, 이왕이면 식의 계산 결과가 가장 큰 해석을 찾아보기로 했다. 마법천자문 정주행에 바쁜 연두를 대신해 여러분이 그 결과를 대신 찾아주자.

올바른 해석의 정의는 다음과 같다.

  • 올바른 해석은 <수>, <수><연산자><수>, <수><연산자><수><연산자><수>, … 의 꼴이어야 한다.
    • 즉, <수>로 시작해서 <수>로 끝나며, <수>와 <연산자>가 번갈아가며 위치해야 한다.
  • <수>는 +-, +, - 중 하나이며, 각각 1111, 1010, 11로 해석된다.
  • <연산자>는 +, - 중 하나이며, 각각 더하기, 빼기로 해석된다.
    • -를 음의 부호로는 쓸 수 없는 것에 주의하자. 예를 들어, --는 −1-1이 될 수 없다.

입력

첫 번째 줄에 +, -로 이루어진 길이가 200 000200\,000 이하인 문자열이 주어진다.

반드시 하나 이상의 올바른 해석이 존재하는 입력만 주어진다.

출력

주어진 문자열의 올바른 해석 중, 가장 큰 계산 결과를 출력한다.

예제3

  1. 예제 1

    입력
    +----+-+-
    
    예상 출력
    10
    
  2. 예제 2

    입력
    --+-+-
    
    예상 출력
    -9
    
  3. 예제 3

    입력
    -
    
    예상 출력
    1