영숙의 게임
| 실행 시간 제한 | 메모리 제한 |
|---|---|
| 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을 합치는 것은 최적의 방법이 아니라는 점을 참고하세요.