파일 업로드

영숙의 게임

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

영숙은 다음과 같은 규칙의 게임을 하고 있습니다

  •  N개의 양의 정수로 이루어진 수열로 시작합니다 (2 <= N <= 248, 각 정수는 1~40 범위)
  • 한 번의 움직임으로 인접한 동일한 두 숫자를 선택하고 그들의 값을 1만큼 더 큰 숫자로 바꿀 수 있습니다.
  • 게임의 목표는 수열에서 가능한 가장 큰 숫자의 값을 최대화하는 것 입니다.
💻 입력

입력의 첫 번째 줄에는 N이 포함되어 있고, 그 다음 N번째 줄에는 게임 시작 시의 N개의 숫자의 수열이 제공됩니다.

🖨️ 출력

영숙이 생성할 수 있는 가장 큰 정수를 출력해주세요.


💻 예제 입력 1
4
1
1
1
2
🖨️ 예제 출력 1
3

💡 힌트

여기서 보여진 예시에서, 영숙은 먼저 두 번째와 세 번째 1을 합쳐서 수열 1 2 2를 얻습니다. 

그 다음 그녀는 두 개의 2를 합쳐서 3을 만듭니다. 처음 두 개의 1을 합치는 것은 최적의 방법이 아니라는 점을 참고하세요.


출처: USACO 2016 US Open Contest, Gold Problem 3. 248