Informatica Online Judge

  햄버거와 샌드위치 [0991 / 03DF]

Time Limit(Test case) : 300 (ms)
Number of users who solved : 7   Total Tried : 125


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

[JKJeong 2014]

Background

경곽이는 햄버거와 샌드위치를 전문으로 하는 가게를 창업했다.

경곽이는 주어진 재료들을 이용하여 햄버거 또는 샌드위치를 만들어서 최대한 이득을 내야한다.

햄버거의 구성은 밑빵("|"), 패티("@"), 윗빵(")")으로 구성되며 완성된 모양은 |@) 가 되며,

샌드위치는 밑빵("|"), 패티("@"), 윗빵("|")으로 구성되며 완성된 모양은 |@|이 된다.

"|"는 햄버거의 밑빵, 샌드위치의 윗빵, 밑빵으로 모두 사용될 수 있으며,
"@"는 햄버거 및 샌드위치의 패티로 사용될 수 있고,
")"는 햄버거의 윗빵으로만 사용될 수 있다.

그리고 경곽이가 창업한 가게의 영업전략 중 가장 중요한 것이 각 재료를 이용하여 빵을 만들 때, 위쪽에 있는 재료일 수록 신선도가 좋아야 한다.

그래야 소비자가 볼 때 전체 신선도를 높게 판단하기 때문이다.

패티나 아래빵이 약간 오래 된 거라도 위빵이 신선하면 전체를 신선하게 본다.

그래서 아래빵보다는 패티를, 패티보다는 위빵이 신선해야 한다.

각 재료와 각 재료의 신선도가 주어질 때, 경곽이가 햄버거 또는 샌드위치를 만들어 판매할 때, 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

단, 신선도가 클 수록 신선한 것이며 모든 재료의 신선도는 다르다.
그리고 햄버거의 판매가격은 2$, 샌드위치의 판매가격은 3$이다.

Input

첫 번째 줄에 재료의 수를 나타내는 정수 N이 입력된다.
두 번째 줄부터 N줄에 걸쳐서 각 재료의 신선도와 종류가 공백으로 구분되어 입력된다.

[입력값의 정의역]
3 <= N <= 10,000
1 <= 신선도 <= 1,000,000,000
각 재료 = { |, @, ) }

[Sub Task Info]
#1 : N <= 30
#2 : N <= 100
#3 : N <= 1,000
#4 : N <= 10,000

Output

주어진 조건을 햄버거 또는 샌드위치를 만들어 판매할 때 얻을 수 있는 최대 수익을 출력한다.

IO Example

입력
4
10 )
5 @
2 |
7 |

출력
3

* 설명 : 위 입력으로 신선도를 고려할 때, 햄버거 1개(신선도 2, 5, 10으로 만든 |@) ) 또는 샌드위치 1개(신선도 2, 5, 7로 만든 |@| )를 만들 수 있다. 하지만 샌드위치를 만드는 것이 더 이득이며 이 때 수익은 3$ 이다.

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