Informatica Online Judge

  Greedy Math [2283 / 08EB]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 5   Total Tried : 3


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (JKJeong 2018)]

Background

경곽이는 사칙연산을 좋아한다.

그래서 매일 같이 칠판에 다음과 같은 수식을 써 놓고 계산하기를 즐긴다.

2+5*4

위 값을 계산하면 그 결과는 22이다.

그런데 갑자기 어느날 재미있는 생각이 들었다. 기존의 우선순위를 무시하고 내가 원하는 순서대로 계산할 경우 그 값을 더 크게 할 수 있다는 사실을 알았다.

예를 들어 위 주어진 식에 다음과 같이 마음대로 괄호를 했다고 생각해보자.

(2+5)*4

그러면 결과는 28이된다. 원래 22였던 값을 계산순서를 적당히 바꾸면 값을 더 크게 할 수 있다는 사실이 놀라웠다.

그래서 경곽이는 어떤 사칙연산 식이 주어질 때 가장 큰 값을 도출하는 방법에 대해서 연구하기로 했다.

경곽이를 도와 주어진 식으로부터 마음대로 연산 순서를 바꿀 수 있다고 할 때, 얻을 수 있는 가장 큰 값을 계산하는 프로그램을 작성하시오.

연산 순서를 마음대로 바꿀 수 있다는 의미는 임의로 괄호를 추가할 수 있다는 의미와 같다.

Input

첫 번째 줄에 사칙연산으로 이루어진 식이 입력된다.

단, 모든 피연산자는 1~9까지의 0을 제외한 한 자리 수이고, 연산자는 "+", "-", "*", "/"으로 표현된다.

그리고 나누기 연산을 할 때 몫으로만 계산하며, "0"으로 나누는 연산은 허용하지 않으므로 "0"으로 나누지 말아야 한다.

[입력값의 정의역]
최대 연산자의 수 <= 100
계산 결괏값은 2^63보다 작다.

입력되는 식은 정상적으로 구성됨이 보장된다.

Output

식으로부터 얻을 수 있는 가장 큰 값을 출력한다.

IO Example

입력1
2+5*4

출력1
28

입력2
1-5-5*5

출력2
21

* 설명 : 다음 순서로 계산하면 21이 된다.

1-5-(5*5)
= 1-5-(25)
= 1-(5-25)
= 1-(-20)
= 21

따라서 21

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]